第二章形式语言与自动机有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata)和不确定的有穷自动机(NondeterministicFiniteAutomata)。确定的有穷自动机DFADFA定义一个DFA的例子：一个DFA可以表示成一个状态图(或称状态转换图)。假定DFAM含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=>”或标以“-”，终态结点用双圈表示或标以“+”，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；DFA的状态图表示一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=>”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。DFA的矩阵表示为了说明DFA如何作为一种识别机制,我们还要理解下面的定义∑*上的符号串t被DFAM接受M=（K，Σ，f，S，Z）若t∑*，f(S，t)=P，其中S为M的开始状态，PZ，Z为终态集，则称t为DFAM所接受（识别）。DFA的确定性表现在转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表Σ含有n个输入字符，那么任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。用程序来模拟DFA的行为DFAM=（K，Σ，f，S，Z）的行为的模拟程序K:=S；c:=getchar;whilec<>eofdo{K:=f(K,c);c:=getchar;};ifKisinZthenreturn(‘yes’)elsereturn(‘no’)ReviewDFAexamplesDFAexamplesFA等价不确定的有穷自动机NFA矩阵表示f为K*到K的子集（2K）的一种映射定理类似DFA,对NFAM=(K，，f，S，Z)也有定义∑*上的符号串t被NFAM接受也可以这样理解Examples(0|1)*(000|111)(0|1)*DFA是NFA的特例.对每个NFAN一定存在一个DFAＭ,使得L(M)=L(N).对每个NFAN存在着与之等价的DFAM。从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态.DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.NFA确定化算法定义对状态集合I的几个有关运算：状态集合I的有关运算的例子NFA的确定化等价的DFANFA的确定化MoreExample作业