编译原理第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？,有四个终态,只有一个终态,DFAM化简的目标,寻找一个状态数比M少的DFAM，使得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.7DFA化简,等价状态和可区别状态,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化简,DFAM=(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,33=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.3NFAM构造正规式R,例：NFAM转换为正规式R，使L(R)=L(M),0,3,1,a,b,a,a,a,b,b,b,a,b,例：NFAM转换为正规式R，使L(R)=L(M),0,3,1,a|b,a,b,a(a|b)*,b(a|b)*,例：NFAM转换为正规式R，使L(R)=L(M),0,a|b,aa(a|b)*,bb(a|b)*,例：NFAM转换为正规式R，使L(R)=L(M),0,a|b,(aa(a|b)*)|(bb(a|b)*),例：NFAM转换为正规式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.2FA转化为右线性文法,右线性文法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.2FA转换为正则文法,S,A,B,a,b,a,b,a,b,GS：,SaA,SbB,S,AaB,AbA,BaS,B,BbA,FA转换为右线性文法GS,3.4.2FA转换为正则文法,左线性文法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.2FA转换为正则文法,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,AAa