编译原理第3章第2节DFA化简与正则文法.ppt

上节回顾,1、DFA和NFA,2、NFA确定化为DFA,(1)、使初态和终态均唯一； (2)、使NFA的每个箭弧上或为单个字符，或为； (3)、NFA中，=a1, , ak, 将NFA确定化： (a)、构造一张含有k+1列的表，置该表首行首列为_Closure(X)； (b)、若某一行第一列已确定，则置第i+1列为Iai，若该行某列未在该表第一列出现过，就将其加入到该表第一列最后一行； (c)、重复上述过程，直至出现在第i+1列上的所有状态子集均在第一列上出现过； (d)、将每个状态子集合并为一个状态，根据得到的状态转换矩阵构造DFA。 (4)、DFA的初态为首行首列的状态，终态为那些含有原终态的状态子集。,遗留问题,1、DFA是否可化简？ 2、如何化简？ 3、怎样才是最简DFA？,有四个终态,只有一个终态,DFA M化简的目标,寻找一个状态数比M少的DFA M，使得 L(M)=L(M)。 最终目标是找到状态最少的那个M。,无关状态1,0,1,2,b,a,a,a,b,多余状态,如何删除多余状态？ （1）寻找没有从其它状态连接的输入弧的状态，把它及其连接的弧去掉； （2）将孤立的TG去掉。,无关状态2,0,2,3,a,a,b,a,死状态,如何删除死状态？ （1）寻找没有连接到其它状态的弧的状态(组)，将该状态(组)及其弧去掉； （2）重复(1)，直到找不到为止。,多余状态和死状态都称为无关状态。,3.2.7 DFA化简,等价状态和可区别状态,0,1,2,a,b,b,b,等价状态：s和t是等价的，如果从s出发能读出某个字w而停在终态，那么同样从t出发也能读出同样的字w而停在终态；反之，若从t出发能读出某个字w而停在终态，那么同样从s出发也能读出同样的字w而停在终态。,b,如果s与t不等价，则称这两个状态是可区别的。,等价状态的情况,若u、v通过所有a弧可以到达的状态等价，那么u、v等价。,若u、v通过a分别到达s、t： 若u能接受aw，则s、t必能接受w，v必可接受aw； 若v能接受aw，则t、s必能接受w， u必可接受aw。,a,到达终态时，终态是可接收空串的，非终态不可以,可区别状态的情况,0,1,2,a,b,b,b,(1) 终态和非终态是可区别的；,(2) 有a弧的和没有a弧的状态可区别的；,有a弧的状态可以接受部分以a为首的字，而没有a弧的状态一定不能接受以a为首的字。,因为s和t可区别，必存在字w，或者s可接受，t不可接受；或者t可接受而s不可接受。 那么对于字aw，或者u可接受v不可接受；或者v可接受而u不可接受。,(4) u有a弧到达s，对s的任意等价状态t，v均没有a弧到达，则u, v可区别。,假设u、v等价，若s可接受字w，则u、v可接受字aw，v通过a弧到达的状态必能接受w；反之，若v通过a弧到达的状态能接受字w，则u、v可接受aw，s可接受w。这样v通过a弧达到的状态与s等价，矛盾。,状态集划分,0,1,2,a,b,b,b,(1) 终态和非终态是可区别的；,(2) 有a弧的和没有a弧的状态可区别的；,(1) 终态和非终态是可区别的；,(2) 1、2有b弧到达3，0没有。,(4) u有a弧到达s，t是s的等价状态，v没有到达t的a弧，则u, v可区别。,DFA化简,DFA M=(S, , f, S0, Z)，状态子集划分算法：,(2) 将S的终态和非终态分开，形成基本划分=S-Z, Z，中属于两个不同子集状态是可区别的；,(1) 消除无关状态；,(3) 若某一时刻=I(1), I(2), , I(m)，且属于不同子集的状态是可区别的，检查每个I(k)是否能进一步划分： 对任意字符a，若I(k)中有状态s1和s2经a弧分别到达t1和t2，且t1和t2属于的不同子集，则将I(k)一分为二： I(k1)=s|sI(k)且s经a弧到达t1所在子集中的状态 I(k2)=I(k)-I(k1),(4) 重复执行(3)，直到中的每个子集都不能再划分为止；,(5) 合并等价状态。,例：将下面的DFA化简,(1) 消除无关状态。,(2) 初次划分： 0=0,1,2, 3,4,5,6,(3) 考察0,1,2： f(0,a)=10,1,2; f(1,a)=33,4,5,6; f(2,a)=10,1,2; 1=0,2,1,3,4,5,6,(4) 考察0,2：f(0,b)=20,2; f(2,b)=43,4,5,6; 2=0, 2, 1, 3,4,5,6,(4)2=0, 2, 1, 3,4,5,6,(5) 考察3,4,5,6：f(3,a)=33,4,5,6; f(4,a)=63,4,5,6; f(5,a)=63,4,5,6; f(6,a)=33,4,5,6;,f(3,b)=53,4,5,6; f(4,b)=43,4,5,6; f(5,b)=43,4,5,6; f(6,b)=53,4,5,6; 最后划分：3=0, 2, 1, 3,4,5,6,例：将下面的DFA化简,(6) 根据最后划分：3=0, 2, 1, 3,4,5,6，合并等价状态。,0,1,2,a,a,a,a,b,b,b,b,(7) 确定初态和终态。,例：将下面的DFA化简,合并状态后创建关系的原则,两个状态集之间：S=s1,s2,sm, T=t1,t2,tn,(1) 从si到tj全部有a弧：,从S到T引a弧,(2) 部分si到tj有a弧，部分没有：,说明S可划分,(3) 全部si到部分tj有a弧，到部分tj没有：,从S到T引a弧,(4) 从si到tj全部没有a弧：,从S到T没有a弧,合并状态后创建关系的原则,两个状态：S=s1,s2,sm, T=t1,t2,tn,(1) 从si到tj全部有a弧：从S到T引a弧；,(2) 部分si到tj有a弧，部分没有：说明S可划分；,(3) 全部si到部分tj有a弧，到部分tj没有：从S到T引a弧；,(4) 从si到tj全部没有a弧：S到T没有a弧。,S=T的情况：,(1) 从si到sj全部有a弧：从S到自身引a弧；,(2) 部分si到sj有a弧，部分没有：说明S可划分；,(3) 全部si到部分sj有a弧，到部分sj没有：从S到自身引a弧；,(4) 从si到sj全部没有a弧：S到自身没有a弧。,例DFA化简,(1) 消除无关状态；,(2) 首次划分：0=1,2,4,5,6,7, 0,3,(3) 考察1,2,4,5,6,7，由0弧： , ,(3) 考察1,2,4,5,6,7，由0弧：1 , ,(3) 考察1,2,4,5,6,7，由0弧：1 , 2 ,(3) 考察1,2,4,5,6,7，由0弧：1 , 2,4 ,(3) 考察1,2,4,5,6,7，由0弧：1 , 2,4,5 ,(3) 考察1,2,4,5,6,7，由0弧：1,6 , 2,4,5 ,(3) 考察1,2,4,5,6,7，由0弧：1,6 , 2,4,5,7 ,故：1=1,6,2,4,5,7, 0,3,(4)考察1,6，不能划分。,(5)考察2,4,5,7， 2=1,6, 2,5, 4,7, 0,3,例DFA化简,(6)最终划分： =1,6, 2,5, 4,7, 0,3,2,5,4,7,1,6,0,1,0,1,0,1,0,1,例DFA化简,(1) 消除无关状态；,(2) 首次划分：0=0, 1,2,3,4,5,(3) 考察1,2,3,4,5，由0弧： 1=0 , 1,5, 2,3,4,(4) 考察1,5：1,500, 1,513, 不能划分： 2=0 , 1,5, 2,3,4,(5) 考察2,3,4，由0弧不能划分；由1弧： 2,4, 3 3=0 , 1,5, 2, 4 ,3,例DFA化简,(6) 考察2,4：2,403, 2,410, 不能划分,(7) 最终得到：0, 1,5, 2,4, 3,(5) 3=0 , 1,5, 2, 4 ,3,例DFA化简,根据最终划分构造DFA：0, 1,5, 2,4, 3,2,4,3,1,5,1,0,0,1,0,1,0,1,前期内容回顾,1、一个语言可以用正规式描述；,2、正规式容易构造出NFA进行描述；,3、NFA可以确定化为DFA，而DFA编程实现无回溯；,4、DFA可以进一步化简以减少状态数量，进一步简化程序编制；,每个NFA是否也可以用正规式描述？如何转换？,i,j,SA*T,i,j,A,k,B,i,j,A,B,i,j,S,k,T,A,使NFA的弧上仅含单个输入字符或的过程是逐步分解的过程；NFA构造正规式的过程是逐步合并的过程。,3.3 NFA M构造正规式 R,例：NFA M转换为正规式 R，使L(R)=L(M),0,3,1,a,b,a,a,a,b,b,b,a,b,例：NFA M转换为正规式 R，使L(R)=L(M),0,3,1,a|b,a,b,a(a|b)*,b(a|b)*,例：NFA M转换为正规式R，使L(R)=L(M),0,a|b,aa(a|b)*,bb(a|b)*,例：NFA M转换为正规式R，使L(R)=L(M),0,a|b,(aa(a|b)*) | (bb(a|b)*),例：NFA M转换为正规式R，使L(R)=L(M),0,a|b,(aa(a|b)*) | (bb(a|b)*),(aa|bb)(a|b)*,(a|b)*(aa|bb)(a|b)*,R= (a|b)*(aa|bb)(a|b)*,正则文法（3型文法）,正则文法的产生式形式为：AB或A 或者AB或A, 其中A,BVN，VT , VT,单词既可用正则文法表示，也可用正规式表示。 正则文法、正规式、DFA、NFA是等价的。,3.4.1 正则文法转换为FA,文法GA：AaA, Aa, AbB, BaA,A,abaa的识别过程：,A,aA,abB,abaA,abaa,3.4.1 正则文法转换为FA,文法GA：AaA, Aa, AbB, BaA,abaa的识别过程：,A,A,a,a,右线性文法GS转换为FA：,AVN表示状态，S为初态。,(2) 增加一个状态Z作为终态。,(3) 对形如AtB的每条产生式，画一条A到B的t弧,(4) 对形如At的每条产生式，画一条A到Z的t弧。,右线性文法GS转换为FA,3.4.1 正则文法转换为FA,SaA,SbB,S,AaB,AbA,BaS,BbA,B,S,A,B,a,b,a,b,a,b,右线性文法GS转换为FA,3.4.1 正则文法转换为FA,文法GZ：ZU0, ZV1, UZ1, U1, VZ0, V0,1010的识别过程：ZU0Z10U0101010,S,Z,1,左线性文法GZ转换为FA：,AVN表示状态，Z为终态。,(2) 增加一个状态S作为初态。,(3) 对形如ABt的每条产生式，画一条B到A的t弧。,(4) 对形如At的每条产生式，画一条S到A的t弧。,左线性文法GS转换为FA,3.4.1 正则文法转换为FA,ZU0,ZV1,UZ1,U1,VZ0,V0,S,U,V,0,1,1,1,0,0,左线性文法GS转换为FA,3.4.2 FA转化为右线性文法,右线性文法GS转换为FA：,AVN表示状态，S为初态。,(2) 增加一个状态Z作为终态。,(3) 对形如AtB的每条产生式，画一条A到B的t弧。,(4) 对形如At的每条产生式，画一条A到Z的t弧。,FA转换为右线性文法：,(2) 对每条A到B（非终态）的t弧，增加产生式AtB。,(3) 对每条A到终态的t弧，增加产生式At。,(1) 初态S为G的开始符号。,3.4.2 FA转换为正则文法,S,A,B,a,b,a,b,a,b,GS：,SaA,SbB,S,AaB,AbA,BaS,B,BbA,FA转换为右线性文法GS,3.4.2 FA转换为正则文法,左线性文法GZ转换为FA：,AVN表示状态，Z为终态。,(2) 增加一个状态S作为初态。,(3) 对形如AtB的每条产生式，画一条B到A的t弧。,(4) 对形如At的每条产生式，画一条S到A的t弧。,FA转换为左线性文法：,(2) 对每条A（非初态）到B的t弧，增加产生式BtA。,(3) 对每条初态A到B的t弧，增加产生式Bt。,(1) 终态Z为G的开始符号。,FA转换为文法GS,3.4.2 FA转换为正则文法,S,U,V,0,1,1,1,0,0,GZ：,V0,U1,ZU0,ZV1,VZ0,UZ1,Axy,Ax|y,Ax*,Ax*y,Ax*B, By,AxA, Ay,3.4.3 正规式转换为右线性文法,(1) VT=；,(2) 对于正规式R，生成产生式SR，并将S定为G的开始符号；,(3) 对已有的产生式，按以下原则进行变换，直到每个产生式只有一个终结符号为止：,(4) 第(3)步所确定的产生式组为P，而非终结符号组成VN。,3.4.3 正规式转换为右线性文法,例：将正规式R=a(a|b)*b转换为正规文法G，并使L(G)=L(R).,(1) 确定VT=a,b；,(2) 确定G的开始符号为S，且形成正规式Sa(a|b)*b；,(3) 对Sa(a|b)*b，重写成：SaA, A(a|b)*b；,(4) 对A(a|b)*b，重写成：A(a|b)A, Ab； 可整理为：AaA, AbA, Ab；,(5) 最终产生式集P： SaA, AaA, AbA, Ab,(6) VN=S, A,Axy,Ax|y,Ax*,Axy*,Ax, AAy,3.4.3 正规式转换为左线性文法,例：将正规式R=a(a|b)*b转换为左线性正规文法G，并使L(G)=L(R).,(1) VT=a, b；,(2) 开始符号为S, Sa(a|b)*b；,(3) 对 Sa(a|b)*b：SAb, Aa(a|b)*；,(4) 对 Aa(a|b)*：Aa, AA(a|b) ； 整理为：Aa, AAa, AAb,(5) 最终产生式： SAb, Aa, A