《词法分析作业答案.ppt》由会员分享，可在线阅读，更多相关《词法分析作业答案.ppt（11页珍藏版）》请在三一办公上搜索。
1、,1.求正则式（a|b)(a|b|0|1)*对应的正则文法（右线性文法），画状态转换图。解:(a|b):S a|b(a|b|0|1)*:A aA|bA|0A|1A合并:S a|b A aA|bA|0A|1A|,2、求正则文法GZ：Z 0Z|1Z|0A A 0B B 0 对应的正则式:解:(0|1)*000,2.已知有限自动机如图,(1)以上状态转换图表示的语言有什么特征？(2)写出其正规式与正规文法.(3)构造识别该语言的有限自动机DFA.,解：（1）L=W|W 0,1,并且W至少有两个连续的1（2）正则式为（0|1)*11(0|1)*正则文法G(Z)为：Z0Z|1Z|1A A 1B|1 B
2、0B|1B|0|1（3）将图中有限自动机确定化：首先从处态A出发：,I I0 I1(1)A(1)A(2)A,B(2)A,B(1)A(3)A,B,C(3)A,B,C(4)A,C(3)A,B,C(4)A,C(4)A,C(3)A,B,C其相应的DFA如下图：,将这个DFA最小化：首先分终态和非终态两个集K1=1,2 和 K2=3,4 由于状态1输入1到达状态K1集，而状态2输入1到达K2集故将k1分为K11=1,K12=2 由于状态3，和 4 输入1，或0 都到达k2集所以状态3，4等价。则可以分割成三个子集：1，2，3，4,所以将DFA最小化的状态图如下：,3.请构造与正则式R=(a*b)*ba(
3、a|b)*等价的状态最少的DFA（确定有限自动机）解：（1）首先构造转换系统图：（2）由系统转换图构造DFA（NFA确定化）设初态为S,A,B,G,F,NFA确定化为DFA的过程：I Ia Ib(1)S,A,B,G,F(2)G,F(3)A,B,C,G,F(2)G,F(2)G,F(4)A,B,G,F(3)A,B,C,G,F(5)D,F,G,E,Z(3)A,B,C,G,F(4)A,B,G,F(2)G,F(3)A,B,C,G,F(5)D,F,G,E,Z(6)G,F,E,Z(7)A,B,E,Z,G,F(6)G,F,E,Z(6)G,F,E,Z(7)A,B,E,Z,G,F(7)A,B,E,Z,G,F(6)
4、G,F,E,Z(8)A,B,C,E,Z,G,F(8)A,B,C,E,Z,G,F(5)D,F,G,E,Z(8)A,B,C,E,Z,G,F DFA 这状态图如下：,确定有限自动机图如下：,（3）将DFA最小化：先将终态和非终态分成两个集:K1=1,2,3,4,K2=5,6,7,8 对于K1中的3态输入a则进入K2集，而1，2，4态输入a仍然在K1中，故K1可一分为二K11=1,2,4和K12=3;考察K11对于1，4态输入b到达3态而2态输入b到达4态。故K11可一分为二K111=1,4;K112=2最后考察K2输入a或b都到达K2集。则DFA化简为1，4，2，3，5，6，7，8四个子集。其状态图如下：,
