RG、FA、RE等相互之间的转换ppt课件

1、10M=( , ,)G=(, ,)NTQf q ZVVS P自动机 正则文法 23 4567891011P56 第2-24（1）将正规式：(a|b)*a(a|b)转换为最简的确定有限自动机。【解】先转换为NFA：qs012qZaa,bab12IIaIbqs,0,10,1,20,10,1,20,1,2,qz0,1,qz0,10,1,20,10,1,2,qz0,1,2,qz0,1,qz0,1,qz0,1,20,1NFA的确定化表Qab0121342123*344*12重命名后的DFAQab0101232*233*10化简后的DFA131415161718左线性左线性文法和右线性右线性文法之间存在一

2、定关系。l 一个左线性文法GL存在一个等价的右线性文法GR。l 一个右线性文法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。2122则右线

3、性文法 （，S）,其中:=A,B,S=0,1P: S 0A|1A |0B |1BA 0B 1则L(GR)=00,01,10,11。所以L(GL)= L(GR),说明左线性文法 和右线性文法 是等价的。2324v（）合并）合并v符号合并符号合并转换函数初态NFA M (S,S0,F)SS的子集多值映射S0 S非空初态DFA M (S,s0,F)SS单值映射s0S唯一的初态NFA允许允许边出现边出现（）合并：）合并：如果有S1S2,则把S2状态合并到S1状态。25例1：NFA转换成DFA (符号合并)例2：设计一个DFA，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。aa3cb012

4、a01,2cb30,10ZCSAB1解：解：根据题意，得出相应的正规式：0(0|1)*1 得状态转换图(NFA)如下：2601stateDFA stateSS,ABCSABCS,ABCS,ABCABCBCBCZ ABC,BC,BCZS,ABC,BC,BCZBCBCBCZ BC,BCZS,ABC,BC,BCZBCZBCBCZ BCZS,ABC,BC,BCZ(S,)=;(S,0)=？(S,0)=A; (A,)=B; (B,)=C; (C,)=； 0,10ZCSAB12701stateDFA stateSS,ABCSABCS,ABCS,ABCABCBCBCZ ABC,BC,BCZS,ABC,BC,B

5、CZBCBCBCZ BC,BCZS,ABC,BC,BCZBCZBCBCZ BCZS,ABC,BC,BCZ 0,10ZCSAB1(ABC,0)初态初态(S,0)28得状态转换图(DFA)如下：000SCA101B1000SBCZABC101BC1在DFA中，所有含有NFA的终态的状态作为DFA的终态DFA M=( S,A,B,C , 0,1 , , S , C )其中其中如上（不可省略）293031初态初态3233343536v将所有DFA的终态与其它状态划分成两个子集G1,G2;v分别从两个子集G1,G2中寻找等价状态进行化简。37v将所有DFA的终态与其它状态划分成两个子集3839例2：设计一个DFA，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。化简01SABCABCBCBCZBCBCBCZBCZBCBCZ01SABCABCABCBCZBCZABCBCZDFA M=( S,ABC,BCZ , 0,1 ,