资源描述：
《编译原理答案(部分).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理第三章词法分析作业答案说明：以下答案仅供同学们参考，有问题的地方欢迎指正。同时，我们希望同学们更好的通过网上答疑资源与我们进行讨论。7.构造下列正规式相应的DFA。（1）（1）1（0
2、1）*101解：首先构造NFA如下：判断：由状态1接受字符1后可能会到状态1或状态2，故上述状态图为NFA。现在将其确定化。（引进新的初态节点X和终态节点Y，从X到状态1以及从状态4到Y均连一条e箭弧）II0I1{X，0}0—{1}1{1}1{1}1{1，2}2{1，2}2{1，3}3{1，2}2{1，3}3{1}1{1，2，4，Y}4{1，2，4，Y}4{1，3}3{1，2
3、}2则，DFA如下：***（2）（2）1（1010
4、1（010）1）0解：构造NFA如下：II0I1{1}—{2}21{2}{9}4{3}32{3}{4，7}5{2，6}63{9}——4{4，7}5—{2，5，8}7{2，6}6{9}4{3}3{2，5，8}7{2，3，8，9}8{3}3{2，3，8，9}8{2，4，7，8，9}9{2，3，6}14{2，4，7，8，9}9{2，8，9}10{2，3，5，8}11{2，8，9}10{2，8，9}10{3}3{2，3，5，8}11{2，3，4，7，8，9}12{3}3{2，3，4，7，8，9}12{2，4，7，8，9}
5、9{2，3，5，6，8}13{2，3，5，6，8}13{2，3，4，7，8，9}12{2，3，6}14{2，3，6}14{4，9}15{2，3，6}14{4，9}15—{5}16{5}{3}—163DFA构造如下：（注：本题可能会有多种解法，上述答案仅供参考。另外，有兴趣的同学可对上述所得到的DFA进行化简，从而可得最简答案。）****（3）0101010解：构造状态图如下：经观察可知，上述状态图即为DFA。****（4）（00
6、11）（（01
7、10）（00
8、11）（01
9、10）（00
10、11））解：构造NFA如下（其中没有标明接受字符的线上均为e）：对上述NFA进
11、行确定化并最小化后，最终结果为：（具体解题过程从简）8-(1).(0
12、1)*018-(4).(A
13、a)*(B
14、b)*......(Z
15、z)*9-(1).(0
16、1)*010(0
17、1)*9-(2).1*(0
18、111*)*1*12.将图2.16所示的状态转换图表示的FA分别确定化和最小化。bab023aa,bbaaab01145abbb(a)(b)图2.16状态转换图解：(1)对图(a)1确定化过程为：ε_closure({0})={0},A(初态)ε_closure(smove(A,a))={0,1},Bε_closure(smove(A,b))={1},Cε_clo
19、sure(smove(B,a))={0,1},Bε_closure(smove(B,b))={0,1},Bε_closure(smove(C,b))={0},ADFA如图：a,baABbbC最小化DFA过程：初始划分为：{{A,B},{C}};C自身一组，不能再分；AB在一组，查看它们的状态转移：move(A,a)=Bmove(A,b)=Cmove(B,a)=Bmove(B,b)=B∴A,B可区分,新的划分为：{{A},{B},{C}},即最后划分∴此DFA已经是最小化的（2）对图(b)①经观察，原图即为确定化的DFA②最小化DFA：move(0,a)=1;mov
20、e(0,b)=2;move(1,a)=1;move(1,b)=4;move(2,a)=1;move(2,b)=3;move(3,a)=3;move(3,b)=2;move(4,a)=0;move(4,b)=5;move(5,a)=5;move(5,b)=4;初始划分为：P0={{0,1},{2,3,4,5}};观察第一个子集{0,1},在读入a后，都到达同一个状态1；第二个子集{2,3,4,5}，在读入输入符号a后，状态2和4分别转换为第一个子集中的状态1和0，状态3和5分别转换为第二个状态中的3和5,这就意味着{2,4}中的状态和{3,5}中的状态在读入a后到达
21、了不等价的状态，因此得到了新的划分P1如下：P1={{0,1},{2,4},{3,5}}观察P1中的第一个子集{0,1}，在读入b后分别到达第二个子集中的状态2和4；第二个子集{2,4}，在读入b后分别到达第三个子集中的状态3和5;第三个子集{3,5}，在读入b后分别到达第二个子集中的状态2和4。经过考察，P1已经不能在化分了。令1代表{0,1}消去0,令2代表{2,4}消去4,令3代表{3,5}消去5，最后得到最小化的DFA如下：ab01abb2a14.(0
22、10)*编译原理第四章语法分析—自上而下分析作业参考答案说明：以下答案仅供同学们参考，有问题的地方欢迎指
23、正。同时，
