编译原理课后答案第四章参考答案

第四章参考 第1： (1) 0,1 1 1 0 1 Z 确定化： I0 I1 –S A A A AB AB AC AB AC A ABZ +ABZ AC AB S A B C Z 重新命名，令{AB}为B、{AC}为C、{ABZ}为Z 其中S为初态，Z为终态 0 1 –S A A A B B C B C A D +Z C B (3) 确定化： Ia Ib –S A A AB AZ AB AB ABZ +AZ AB AZ +ABZ AB ABZ 0 1 2 3 4 重新命名，以0、1、2、3、4代替{S},{A}, {AB},{AZ},{ABZ}得DFA 其中0为初态，3，4为终态 Ia Ib –0 1 1 2 3 2 2 4 +3 2 3 +4 2 4 第2题： I0 I1 –X Z X +Z XZ Y +XZ XZ XY Y XY XY XYZ X +XYZ XYZ XY A B C D E F 重新命名，以A、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ代替{X},{Z },{XZ },{ Y },{ XY },{XYZ}得DFA 其中A为初态，Ｂ，Ｃ，Ｆ为终态 0 1 –A B A +B C D +C C E D E E F A +F F E 第3题： 确定化： . I0 I1 –S VQ QU VQ VZ QU QU V QUZ +VZ Z Z V Z . +QUZ VZ QUZ +Z Z Z A B C D E F G 重新命名，以A、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ代替{S},{VQ },{QU },{ VZ },{ V },{QUZ},{Z}得DFA 其中A为初态，D，F，G为终态 . 0 1 –A B C B D C C E F +D G G E G . +F D F +G G G 第4题： (1)确定化： Ia Ib –+0 01 1 +01 01 1 1 0 A B C 重新命名，以Ａ、Ｂ、Ｃ代替{0}、{01}、{1}得ＤＦＡ 其中A为初态，A，B为终态 a b –+A B C +B B C C A 最小化： 初始分划得终态组{A,B}，非终态组{C} Π0：{A,B}，{C} 　　对终态组进行审查，判断A和B是等价的，故这是最后的划分 重新命名，以A、C代替{A,B}、{C}得DFA a b –+A A C C A (2)这是DFA，直接最小化 初始分划得：终态组{0}，非终态组{1,2,3,4,5} Π0：{0}，{1,2,3,4,5} 　　对{1,2,3,4,5}进行审查： 　　∵{4} 输入a后 INCLUDEPICTURE "K:\\GD_jsj_009b\\text\\exam\\test03\\images\\img\\1x1pixel.gif" \* MERGEFORMATINET 到达{0}，{1,2,3,5}输入a后到达{1,3,5}，故得到新分划 {0,1,3,5}，{4} Π1：{0}，{4}，{1,2,3,5} 　　对{1,2,3,5}进行审查： 　　∵{1,5} 输入b后到达{4}，{2,3} 输入b后到达{2,3}，故得到新分划 {1, 5}，{2,3} Π2：{0}，{4}，{1, 5}，{2,3} 对{1, 5}，{2,3}进行审查： 　　{1, 5} 输入a后到达{1, 5} 　　{2} 输入a后到达{1}，{3} 输入a后到达{3}，故得到新分划{2}，{3} Π3：{0}，{2}，{3}，{4}，{1, 5} 　　这是最后分划了 重新命名，以0，2，3，4，1代替{0}，{2}，{3}，{4}，{1, 5}得DFA略 第7题 首先判断E，F为多余状态 根据正则文法转化为NFA的构造NFA 确定化： Ia Ib --( a b –S A Q –0 1 2 A A BZ 1 1 3 Q Q DZ 2 2 4 +BZ Q D +3 2 5 +DZ A B +4 1 6 D A B 5 1 6 B Q D 6 2 5 0 1 2 3 4 5 6 最小化： 初始分划得：终态组｛3,4｝，非终态组｛0,1,2,5,6｝ Π0：｛3,4｝,｛0,1,2,5,6｝ 对｛0,1,2,5,6｝进行审查： {1,2}输入b到达｛3,4｝，而{0,5,6}输入b到达｛2,5,6｝，故得到新分划｛1,2｝,｛0,5,6｝ Π1：｛3,4｝,｛1,2｝,｛0,5,6｝ 对｛0,5,6｝进行审查： {0}经过b到达｛２｝，{5,6}经过b到达｛5,6｝，故得到新分划｛0｝｛5,6｝ Π3：{0}，{1,2}，{3,4}，{5,6} 　　这是最后划分了。 重新命名，以0，1，3，5代替{0}，{1,2}，{3,4}，{5,6}得DFA略 第9题 这是DFA，直接最小化 初始分划得：终态组｛6,7｝，非终态组｛1,2,3,4,5｝ Π0：｛6,7｝,｛1,2,3,4,5｝ 对｛1,2,3,4,5｝进行审查： {1,2}输入b到达｛2｝，而{3,4}输入b到达｛6,7｝，{5}输入b不会有任何动作，故得到新分划｛1,2｝,｛3,4｝,{5} Π1：｛6,7｝,｛3,4｝,｛5｝,｛1,2｝ 这是最后划分了。 重新命名，以1，3，5，6代替｛1,2｝,｛3,4｝,｛5｝,｛6,7｝得DFA 所识别的语言是b*a (c| da)*bb* 第11题 根据正则文法（左线性文法）转化为NFA的方法构造NFA： 确定化： Ia Ib --( a b –+ZS A A –+0 1 1 A AS 1 2 +AS AS A +2 2 1 0 1 2 重新命名，以0、1、2代替{ZS}、{A}、{AS}得DFA 其中0为初态，0，2为终态 所识别的语言是：ε| (a|b) a (ba|a)* 第13题 （1） 假设d {A,B,…,Y,Z} n {0,1,2,…,8,9}，文法可以等价得化为： <单词>—> <标识符> | <整数> <标识符>—> <标识符>d | <标识符>n | d <整数>—><整数>n | n （2） 根据正则文法（左线性文法）转化为NFA的方法构造NFA： 重新命名状态，令A、B、C分别代<单词>、<标识符>、<整数> C B A S S d,n d ε a a b a S ε A a a,b a 2 1 0 A b b B Z Q a A S a Z a b a D b b b b b a b b a d c 6 b a 5 3 1 B n C ε n b a b Z B A S a a,b a