RGFARE等相互之间的转换

1、0m=( , ,)g=(, ,)ntqf q zvvs p自动机 正则文法 p56 第2-24（1）将正规式：(a|b)*a(a|b)转换为最简的确定有限自动机。【解】先转换为nfa：qs012qzaa,babiiaibqs,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化简后的dfa左线性左线性文法和右线性右线性文法之间存在一定关系。l 一个左线性文法gl存在一个等价的右线性文法g

2、r。l 一个右线性文法gr存在一个等价的左线性文法gl 。可见，可见，gl和和gr是等价的，也就是说，给定一个右线性是等价的，也就是说，给定一个右线性文法可以构造对应的左线性文法。同样，给一个左线性文法可以构造对应的左线性文法。同样，给一个左线性文法也可以构造一个右线性文法。文法也可以构造一个右线性文法。上述等价关系规定开始符号s不能出现在规则左部不能出现在规则左部。例：例： 设左线性文法 （， s，），其中: =a,b,s =0,1 p: s a0|b1 a 0|1 b 0|1则l(gl)=00,01,10,11。则右线性文法 （，s）,其中:=a,b,s=0,1p: s 0a|1a |0b

3、 |1ba 0b 1则l(gr)=00,01,10,11。所以l(gl)= l(gr),说明左线性文法 和右线性文法 是等价的。v（）合并）合并v符号合并符号合并转换函数初态nfa m (s,s0,f)ss的子集多值映射s0 s非空初态dfa m (s,s0,f)ss单值映射s0s唯一的初态nfa允许允许边出现边出现（）合并：）合并：如果有s1s2,则把s2状态合并到s1状态。例1：nfa转换成dfa (符号合并)例2：设计一个dfa，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。aa3cb012a01,2cb30,10zcsab1解：解：根据题意，得出相应的正规式：0(0|1)

4、*1 得状态转换图(nfa)如下：01statedfa 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,10zcsab101statedfa statess,abcsabcs,abcs,abcabcbcbcz abc,bc,bczs,abc,bc,bczbcbcbcz bc,bczs,abc,bc,bczbczbcbcz bczs,abc,

5、bc,bcz 0,10zcsab1(abc,0)初态初态(s,0)得状态转换图(dfa)如下：000sca101b1000sbczabc101bc1在dfa中，所有含有nfa的终态的状态作为dfa的终态dfa m=( s,a,b,c , 0,1 , , s , c )其中其中如上（不可省略）初态初态v将所有dfa的终态与其它状态划分成两个子集g1,g2;v分别从两个子集g1,g2中寻找等价状态进行化简。v将所有dfa的终态与其它状态划分成两个子集例2：设计一个dfa，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。化简01sabcabcbcbczbcbcbczbczbcbcz01sabcabcabcbczbczabcbczdfa m=( s,abc,bcz , 0,1