第二章-形式语言与自动机理论基础(有限自动机).ppt

2.2有限自动机,(DeterministicFiniteAutomata)一.DFA的定义二.DFA的三种表示三.DFA接受的语言,2.2.1确定的有限自动机(DFA),一DFAM定义一个确定的有限自动机DFAM是一个五元组（，S，S0，Z，f）,是一个字母表，它的每个元素称为一个输入符号。,S是一个有限状态集合。,S0S，S0称为初始状态。,Z是S的子集，称为终结状态集合。,f是一个从S到S的单值映射f(，)（,S，）表示当前状态为q,输入符号为a时，自动机将转换到下一个状态，称为的后继。,例设（，f）其中f（，），f（，）f（，），f（，）f（，），f（，）f（，），f（，）,二的三种表示：（1）用转换函数（2）转移矩阵（3）状态转换图,所谓确定的状态机，其确定性表现在状态转移函数是单值函数！,（1）用转换函数,f（，），f（，）f（，），f（，）f（，），f（，）f（，），f（，）,（2）转移矩阵,横坐标,纵坐标,0,1,3,2,a,a,a,a,b,b,b,b,3,（3）状态转换图,结点表示状态，箭弧标记为字母表中的字母,终结状态如何表示？,三DFAM接受的语言(字符串集)如果对所有*，以下述方式递归地扩充f的定义f（，）f(，）f(f(，w），）,对于上例中的DFAM和w=baa，f(0，baa）=f(2,aa）=f(1,a）=3,0,1,3,2,a,a,a,a,b,b,b,b,3,0,b,2,a,1,a,该DFAM能够识别字符串baa,从状态转换图看，从初态出发，沿任一条路径到达终结状态，这条路径上的弧上的标记符号连接起来构成的符号串为DFAM所识别。DFAM所能识别的符号串的全体记为L(M)，称为DFAM所识别的语言。,（）*，若存在Z，使f（，）,2.2.2非确定的有限自动机（NFA）NondeterministicFiniteAutomata,一.NFAm的定义二.FA的等价定理三.具有-转移的NFA构造DFA的算法,非确定有限自动机M是一个五元组M（，S，S，Z，f）其中，S，Z的意义和DFA的定义一样，其中S表示初始状态集，f是一个从S()到S的子集的映射，即f：S()S，其中S是S的幂集，即S中所有子集组成的集合。,一NFA的形式定义:,确定的和非确定的有限自动机之间的重要区别是1、状态转换函数是一个多值映射；反映在状态转换图上即对同一弧标记到达的状态结点不惟一。2、NFA初态集，而DFA是一个唯一的状态.NFA存在弧标记,0,1,3,2,a,b,a,b,b,a,b,3,类似FA，NFAm可用状态转换图表示，如果f(，）=1，2.，k，则从q出发分别向1，2.，k各画出一条标记为a的箭弧(非确定的含义)。同理可定义NFAm所识别（接受）的语言。*中所有可能被NFAm所识别的符号串的集合记为L(M)。,NFAM所识别的语言为:L(M)=|f(q0,)=qqZ,定理对任何一个NFAM，都存在一个DFAM，使L(M)=L(M)构造方法：用M的一个状态对应M的多个状态，用这种方法，能从一个NFAM构造一个等价的DFAM，称作子集构造法。,二.FA的等价定理,NFAM=(S,f,S0,Z)等价的DFAM=(S,f,S0,Z)S=2S(由NFAM的状态集S的所有子集组成)Z=K|KS且KZ（Z是由至少包含Z中一个状态S的所有子集组成）S0=S0=f(K,a)=P,其中K,PS且P=p|pf(q,a),qkDFAM的f:f(k1,k2,ki,a)=p1,p2,pi当且仅当NFAM的f:f(k1,k2,ki,a)=p1,p2,pi证明（略P30）,定义集合I的-闭包：,令I是一个状态集的子集，定义-closure（I）为：1）若sI，则s-closure（I）；2）若sI，则从s出发经过任意条弧能够到达的任何状态都属于-closure（I）。状态集-closure（I）称为I的-闭包,通过例子来说明状态子集的-闭包的构造方法,三、具有-转移的NFA构造等价DFA的方法,例：如图所示的状态转换图：令I=1，求-closure（I）=？,根据定义：-closure（I）=1，3，5,构造等价DFA算法若t1是NFA的初态，DFA的初态A=closure(t1)。对NFA中每一个箭弧标记m，计算closure(f(q,m)，其中q为已生成的DFA状态。遍历字母表的每个字符为输入例如字母表为a,bB=closure(f(A,a)C=closure(f(A,b)如果B和C不为空集，重复这一过程，直到不在出现新的状态集合）D=closure(f(B,a)E=closure(f(B,b)F=closure(f(C,a)G=closure(f(C,b),注意:D,E,F,G中相等的集合合并,空集则舍去.,closure(f(A，a)的含义NFA中从集合A中的状态出发，先经若干箭弧，接着经标记为a的箭弧到达的状态集合的closure。,0,1,4,2,3,6,5,7,8,9,10,a,a,b,b,b,0,1,2,4,A=0,1,2,4,7,a,3,a,8,6,1,2,4,7,B=3,8,6,1,2,4,7,a,C=5,1,2,4,6,7,从NFA出发构造DFA,b,7,b,5,6,7,1,2,4,a,b,a,b,states,a,b,B=3,8,6,1,2,4,7,A=0,1,2,4,7,B,C=5,6,1,2,4,7,C,B,D=5,9,6,1,2,4,7,D,B,C,B,E=5,10,6,1,2,4,7,E,B,C,等价DFA的转移矩阵,等价的DFA的状态转换图,例：有NFAMA=-closure(1)=1,4,a,B=-closure(f(A,a)=-closure(f(1,4,a)=-closure(f(1,a)f(4,a)=-closure(2,3）=-closure(2,3)=2,3C=-closure(f(A,b)=-closure(f(1,b)f(4,b)=-closure(）=D=-closure(f(A,c)=-closure(f(1,c)f(4,c)=,E=-closure(f(B,a)F=-closure(f(B,b)G=-closure(f(B,c),B=-closure(f(A,a)C=-closure(f(A,b)D=-closure(f(A,c),DFAM的状态图：,A,B,D,C,E,start,1,4,2,3,4,2,a,c,a,b,b,c,3,4,具有-转移的NFA构造等价DFA的方法,不具有-转移的NFA如何构造等价DFA？,例NFAM=(0,1,q0,q1,q0,q1,f),其中f(q0,0)=q0,q1,f(q0,1)=q1f(q1,0)=f(q1,1)=q0,q1,f(q0,0)=q0,q1,f(q0,1)=q1f(q1,0)=,f(q1,0)=q0,q1f(q0,q1,0)=(q0,0)(q1,0)=q0,q1f(q0,q1,1)=(q0,1)(q1,1)=q0,q1,M与M的状态转换图如下所示：,2.2.3确定有限自动机的化简,所谓一个DFAM=(,S,S0,Z,f)的化简是指寻找一个状态数比较少的DFAM,使L(M)=L(M)。而且可以证明，存在一个最少状态的DFAM,使L(M)=L(M)。,自动机是描述信息处理过程的种数学模型对一种语言，它可以用许多文法来描述，同样可以有无限多个FA来描述一种语言；这些FA是等价的，但其构成的复杂程度差别很大,一、有限自动机的多余状态（1）从该自动机的开始状态出发,任何输入串也不能到达的那个状态（2）从该状态出发没有通向终态结的道路,这些多余状态不在从初态到终态的路径上，对识别句子无任何作用。,为什么？,二、等价状态的定义设p,qS，若对任何w*,f(p,w)与f(q,w)同时到达终止状态或拒绝状态之中，则称p和q是等价的。否则，称p和q不等价（可区别）。,判定两个状态p和q不等价，只要找到一个w*，使f（p,w)Z且f（q,w)Z，或者相反。,说明（a）终结状态与非终结状态不等价。,（b）对于a，f（p,a)=r,f（q,a)=s,r与s均等价，则p与q等价;若存在某个a，f（p,a)=r,f（q,a)=s其中r与s不等价,则p与q不等价。,设p表示非终结状态，q表示终结状态，*，使f（p,)=pZ且f（q,)=qZ,r与s不等价,存在w*f（r,w)Z且f（s,w)Zf（p,aw)Z且f（q,aw)Z,分割法：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的.在各个子集中任取一个状态做代表，删去子集的其余状态。,一个DFAm可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的DFAm,分割法具体实现：,有没有多余状态？,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,子集号,终结状态与非终结状态不等价,用子集号代替状态号得:,化简以下DFA,区分终态与非终态,用子集号代替状态号得:,NFA,DFA,最小化,化简过程,正规文法与有限自动机（FA）的等价性,如果对于某个正规文法G和某个有限自动机M，有L(G)=L(M)（正规文法G所产生的语言和某个有限自动机所识别的语言相同）,则称G和M是等价的。,定理2.2对每一个右线性正规文法或左线性正规文法G，都存在一个FAM，使L(M)=L(G),定理2.3对于每一个FAM，都存在一个右线性正规文法G和一个左线性正规文法G，使L(M)=L(G)=L(G)。,正规文法,NFA,DFA,最小化,有限自动机与正规文法（1）有限自动机正规文法（右线性）,例:给出如图FA等价的正规文法G,（2）正规文法（右线性）有限自动机M,2.3正规式（正规表达式）与有限自动机,2.3.1正规表达式与正规集,2.3.2正规式与有限自动机,2.3.1正规表达式与正规集,正规表达式是一种表示法，可以详细描述高级程序语言单词符号的结构或者说每一个正规表达式r表示一个语言L(r).,例如可以用正规表达式表示Pascal语言的标识符（描述标识符的结构），而Pascal语言的标识符（集合）可以看作一个语言，因此正规表达式r实质是用来表示一个语言L(r).Pascal语言的标识符是字母开头的字母数字串，如何表示？,正规表达式的递归定义,字母表上的正规表达式递归定义如下:1.和都是上的正规表达式,它们所表示的语言分别为:和;2.任何a,a是上的正规表达式,它所表示的语言为:a;3.假定r和s是上的正规表达式,它们所表示的语言分别记为L(r)和L(s),那么r|s,rs,r*也都是上的正规表达式,它们所表示的语言分别为L(r)L(s)、L(r)L(s)、L(r)*r|sL(r)L(s)rsL(r)L(s)r*L(r)*一个由正规表达式表示的语言称为一个正规集,规定“*”，“连接”，“”运算左结合，优先级由高到低简化正规式(a)(b)*(c)等价于ab*c例：=A,B,Z,a,b,z,0,1,9正规式1：AB.Zab.z语言1：L(A)L(B)L(Z)L(a)L(b).L(z)=A,B,Z,a,b,z正规式2：01.9语言2：L(0)L(1).L(9)=0,1,9,例=a,b(a)abL(a)L(b)=a,b(b)(ab)(ab)(L(a)L(b)(L(a)L(b)=aa,ab,ba,bb(c)a*(L(a)*=,a,aa,aaa,aaaa,(d)(ab)*(L(a)L(b)*=,a,b,aa,ab,ba,bb,aaa,.(e)aa*b符号串a和包括零个或多于零个a后跟一个b构成的所有符号串,正规式：(AB.Zab.z)(AB.Zab.z)(01.9)*语言：A,B,Z,a,b,z(A,B,Z,a,b,z0,1,9)*,letter(letterdigit)*,Pascal语言的标识符,思考：C+语言的标识符?,正规表达式的代数性质,Kleene闭包r*：任意次的引用，若0次引用则为正闭包r+：一次或多于一次的引用r*=r+r+=rr*,描述单词符号的结构，是进行词法分析程序设计的第一步在表示的基础上如何做进一步的工作？,2.3.2正规式与有限自动机,定理2.5设r是上一个正规表达式，则存在一个FAm接受L(r)。反之亦然。,正规文法，正规表达式和有限自动机三者之间在某种意义下是等价的。字母表上的一个正规语言，既可以由某一个正规文法产生，也可以由某一个正规表达式所表示，还可以由某一个有限自动机识别。,关系图：,正规文法,NFA,正规表达式,DFA,最小化,1.r=2.r=3.r=a,a,q0,q0,q1,q0,q1,a,r=,r=,r=a,1.构造法证明正规表达式与有限自动机等价,start,start,start,1、并运算r=r1r2,q0,q1,f1,f2,q2,f0,m2,m1,r=r1r2,start,r=r1r2,r=r1r2,r=r1*,2、连接运算r=r1r2,q1,f1,q2,m2,m1,f2,r=r1r2,start,3、闭包运算r=r1*,q0,f0,q1,f1,r=r1*,m1,start,例构造与r=1*等价的有限自动机。,q1,q2,1,例构造与r=01*等价的有限自动机。,q1,q2,0,例构造与r=01*1等价的有限自动机。,letter(letter|digit)*,正规表达式,NFA,DFA,最小化,化简过程,对于上任一正规表达式r，一定能构造一个NFAm，使得L(r)=L(m)。首先对NFAm构造一个广义的转换图，其中只有开始状态S和终止状态Z，连接S和Z的有向弧上是正规式R，然后按照下面的替换规则对正规式不断进行分解，不断加入状态结点和箭弧，直到转换图上的所有弧标记都是上的元素或为止。,2.转换法证明正规式与有限自动机的等价,替换规则,代之以,代之以,代之以,从正规式到有限自动机,设=x,y,上的正规式R=xy*(xy|yx)x*，构造一个NFAM，使L(M)=L(R).,letter(letter|digit)*,构造法,转换法,NFA？,正规表达式,NFA,DFA,最小化,化简过程,构造法,转换法,对于上任一NFAm，能构造上一个正规表达式r，使得L(r)=L(m)。把转换图的概念拓广，每条弧上可以用一个正规式标记。首先，在m的转换图上加进S,Z两个结点。从S用弧连接到m的所有初态结点，从m的所有终结（接受）结点用弧连接到Z，从而构成一个新的NFAm，L(m)=L(m)。