《RG、FA、RE等相互之间的转换PPT课件.ppt》由会员分享，可在线阅读，更多相关《RG、FA、RE等相互之间的转换PPT课件.ppt（42页珍藏版）》请在三一文库上搜索。
1、正则文法（RG）,NFA,正则表达式（RE）,1,2,3,4,5,6,DFA,最小化(MFA),实际问题,一、概览,1.对转换函数(A,t)=B，可写成一个产生式:AtB,算法:,2.对可接受状态Z，增加一个产生式：Z,3.有限自动机的初态对应于文法的开始符号, 有限自动机的字母表为文法的终结符号集。,（1）有限自动机正则文法,例：给出如图NFA等价的正则文法G。,【解】 G=（A，B，C，D，a，b，P，A）,其中P: A aB A bD B bC C aA C bD C D aB D bD D ,这是右线性正则文法!,作业 三（1）,算法:, 字母表与G的终结符号相同，即=VT。G的开始符
2、号S是M的初始状态q0;, 为G中的每个非终结符生成M的一个状态，再增加一个新状态Z,作为自动机M的终态，则Q=VNZ。, 对G中的形如AtB的产生式,其中t为终结符或,A和B为非终结符,构造M的一个转换函数f(A,t)=B, 对G中的形如At的产生式,构造M的一个转换函数f(A,t)=Z,（2）正则文法 有限自动机,【例】求与文法GS等价的NFA GS: SaA|bB| AaB|bA BaS|bA|,作业 三（2）,语法制导方法：,1. (a)对于正规式，所构造NFA:,x,y,(b)对于正规式，所构造NFA:,x,y,(c)对于正规式a，a，所构造 NFA:,x,y,a,（3）正规式 有限
3、自动机,2. 若s,t为上的正规式,相应的NFA分别为N(s)和N(t);,(a)对于正规式R=s|t，NFA(R),(b)对正规式R=st，NFA(R),(c)对于正规式R=s*, NFA(R),(d)对R=(s),与R=S的NFA一样.,例:为R=(a|b)*abb构造NFA,使得L(N)=L(R),从左到右分解R，令r1=a，第一个a，则有：,2,a,令r2=b，则有：,4,b,令r3= r1 |r2，则有：,1,4,5,3,2,a,b,作业 三（1）,10,分解R的方法有很多种， 所以结果并不唯一。 阅读P49,11,作业 三（3）,P56 第2-24（1） 将正规式：(a|b)*a(
4、a|b)转换为最简的确定有限自动机。 【解】 先转换为NFA：,qs,0,1,2,qZ,a,a,b,a,b,12,NFA的确定化表,重命名后的DFA,化简后的DFA,（4）有限自动机 正规式,阅读 P50,14,作业 三（4）,(2)消除（合并）M中的所有结点,利用以下转换规则,直至只剩下一个开始符号定义的产 生式,并且产生式的右部不含非终结符.,规则,规则1,规则2,规则3,文法产生式,正规式,AxB,By,AxA|y,Ax,Ay,A=xy,A=x*y,A=x|y,【例】有文法Gs SaA|a, AaA|dA|a|d,【解】: 由AaA|dA|a|d，得： A (aA|dA)|(a|d)A(
5、a|d)A|(a|d) 由规则2得: A=(a|d)*(a|d) 代入S产生式: S a(a|d)*(a|d)|a 于是，有: S=a(a|d)*(a|d)|),（5）正则文法 正规式,算法: （1）对任何正规式r，选择一个非终结符S作为识别符号，并产生 产生式：Sr （2）若x，y是正规式，则对形如Axy的产生式重写为： AxB，By 其中B为新的非终结符，BVN （3）同样: 对于 Ax*y AxA，Ay Ax|y Ax，Ay,【例】将R=a(a|d)*转换成相应的正则文法。,【解】（1）Sa(a|d)*,（2）SaA A(a|d)*,（3）SaA A(a|d)A A,（4）SaA AaA
6、|dA A,（6）正规式 正则文法,18,左线性文法和右线性文法之间存在一定关系。 一个左线性文法GL存在一个等价的右线性文法GR。 一个右线性文法GR存在一个等价的左线性文法GL 。 可见，GL和GR是等价的，也就是说，给定一个右线性文法可以构造对应的左线性文法。同样，给一个左线性文法也可以构造一个右线性文法。,注意：左线性和右线性文法的关系,19,它们之间的等价关系：,上述等价关系规定开始符号S不能出现在规则左部。,20,例： 设左线性文法 （， S，），其中: =A,B,S =0,1 P: S A0|B1 A 0|1 B 0|1则L(GL)=00,01,10,11。,21,由等价关系得:
7、,22,则右线性文法 （，S）,其中: =A,B,S =0,1 P: S 0A|1A |0B |1B A 0 B 1 则L(GR)=00,01,10,11。 所以L(GL)= L(GR),说明左线性文法 和右线性文法 是等价的。,23,非确定的有限自动机NFA与确定的有限自动机DFA从功能上来说是等价的，即：,NFA M,DFA M,构造成一个,使得 L(M)=L(M),二、NFA的确定化,24,（）合并 符号合并,转换思想：,NFA允许边出现,（）合并：如果有S1S2,则把S2状态合并到S1状态。,NFA到DFA的区别：,25,例1：NFA转换成DFA (符号合并),例2：设计一个DFA，其
8、输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。,解：根据题意，得出相应的正规式：0(0|1)*1 得状态转换图(NFA)如下：,26,NFA确定为DFA过程： DFA的初态（为NFA的初始状态经过合并后的状态的并集）例：(S,)=; DFA的其它状态（ 为NFA的状态经过输入符号后产生的状态，再经过合并后的状态的并集）例：求(S,0)=？ (S,0)=A; (A,)=B; (B,)=C; (C,)=； DFA的终态（为所有含有NFA的终态的状态）,0,1,0,C,S,A,B,1,27,NFA确定化过程： (初态、其它状态、终态),0,1,0,C,S,A,B,1,28,得状态转换图(
9、DFA)如下：,在DFA中，所有含有NFA的终态的状态作为DFA的终态,DFA M=( S,A,B,C , 0,1 , , S , C ) 其中如上（不可省略）,29,定义1：集合I的-闭包：,令I是一个状态集的子集，定义-closure（I）为： 1）若sI，则s-closure（I）； 2）若sI，则从s出发经过任意条弧能够到达的任何状态都属于-closure（I）。 状态集-closure（I）称为I的-闭包,为了使得NFA确定化，我们首先给出两个定义：,例：如图所示的状态图： 令I=1，求-closure（I）=？,根据定义： -closure（I）=1，3,30, J是从状态子集I中
10、的每个状态出发，经过标记为a的弧而达到的状态集合., Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过弧到达的状态,定义2: 令I是NFA M的状态集的一个子集, a 定义: Ia=-closure(J) 其中J = (s,a),SI,例：令I=1，求Ia=?,Ia=-closure(J) =-closure(1，a)） =-closure(2，4） =2，4，6,31,例：有NFA M，求DFA M。,I=-closure(1)=1,4 Ia=-closure(1,a)(4,a) = -closure(2,3） = -closure (2,3) =2,3 Ib= -closu
11、re(1,b)(4,b) = -closure(） = Ic= -closure(1,c)(4,c) = I=2,3, Ia=2,Ib=4,Ic=3,4,I Ia Ib Ic,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,初态,32,start,符号,状态,a,b,c,0,2,3,4,1,2,2,1,_,_,_,_,_,_,_,_,3,3,4,4,DFA M状态转换矩阵,将求得的状态转换矩阵重新编号,0,1,4,2,3,1,4,2,3,4,2,a,c,a,b,b,c,3,4,33,“对于任一个DFA，存在一个唯一的状态最少的等价的DFA” 一个有限自动机是化简的
12、 它没有多余状态并且它的状态中没有两个是互相等价的。 一个有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。,三、DFA的化简,34,定义：,(1) 有限自动机的多余状态：从该自动机的开始状态出发，任何输入串也不能到达那个状态。,例:s0为初始状态,画状态图可以看出s4, s6, s8为不可达状态应该消除,35,(2)等价状态 状态s和t的等价条件是:,1) 一致性条件：状态s和t必须同时为可接受状态或 不接受状态. 2) 蔓延性条件：对于所有输入符号,状态s和t必须 转换到等价的状态里.,对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同
13、 的后继，则称s，t是等价的。 （任何有后继的状态和任何无后继的状态一定不等价）,有限自动机的状态s和t不等价,称这两个状态是可区别的。,36,“分割法”：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的.,例1:最小化,状态集的划分 将所有DFA的终态与其它状态划分成两个子集G1,G2; 分别从两个子集G1,G2中寻找等价状态进行化简。,37,解:,(一)区分终态与非终态,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,a,b,区号,区号,将所有DFA的终态与其它状态划分成两个子集,38,区号,区号,区号,39,例2：设计一个DFA，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。化简,DFA M=( S,ABC,BCZ , 0,1 , ,S, BCZ )其中如上(不可省略),40,化简后的DFA:,例3：试求与下图所示NFA等价的化简了的DFA。,41,例4：试构造与正规式R=(a*|b*)b(ba)*等价的状态最少的DFA。,42,注：状态从18标注,NFA确定为DFA:,