编译原理第3章课后习题答案

《编译原理第3章课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理第2版参考习题答案（3章）第3章词法分析3.2.2试描述下列正则表达式定义的语言(1)a(a

2、b)*a答:{aa,aaa,aba,aaaa,aaba,abaa,abba,...},（按穷举法）或以a开头和结尾，长度大于等于2的a,b串（自然语言描述）（2）（（ε

3、a)b*））*答:由a和b组成的任意符号串（3）（a

4、b）*a(a

5、b)(a

6、b)答:倒数第3个符号为a的长度大于等于3的a,b串（4）a*ba*ba*ba*答:有且仅有三个b的由a和b构成的所有串的集合。3.2.5:试写出下列

7、语言的正则定义：（1）包含5个元音的所有小写字母串，这些串中的元音按顺序出现e.g.:{aeiou,xaxeiou,xaxabcxeeiioouu...}consonant->[b-df-hj-np-tv－z]ctnvowels->(consonant*)(((a+)(consonant*))+)(((e+)(consonant*))+)(((i+)(consonant*))+)(((o+)(consonant*))+)(((u+)(consonant*))+)注：consonant为除五元音外

8、的小写字母，记号ctnvowels对应的定义即为题目要求的正则定义。(2)所有由按字典顺序递增序排列的小写字组成的串。a*b*……z*（3)注释，即/*和*/之间的串，且串中没有不在双引号（“）中的*/。head——>/*tail——>*/**incomment->(~(*/)

9、“.”)comment->headincommenttail（9）所有由a和b组成且不含有子串abb的串。**A->b(a︱ab)3.3.1给出3.2.2中正则表达式所描述的语言的状态转换图。(1)a(a

10、b)*a的状态

11、转换图如下：（2）εbεa（3）4aaa2startab501ba6b3b7（4）a*ba*ba*ba*aaaabbb3．6.3使用算法3.25和3.20将下列正则表达式转换成DFA：(1)(2)将（a*

12、b*）*转换成DFANFA：A:ε-closure(0)={0,1,2,3,5,6,7,9,10,11};B:ε-closure(move(A,a))=ε-closure(4)={1,2,3,4,5,6,7,9,10,11}C:ε-closure(move(A,b))=ε-closure(8)

13、={1,2,3,5,6,7,8,9,10,11}ε-closure(move(B,a))=Bε-closure(move(B,b))=C;ε-closure(move(C,a))=Bε-closure(move(C,b))=C;DFA如下：3）（（

14、a）b*）*解：1’按以下步骤：1.子表达式r1，即表达式;2.r2,即第一个a;3.r3=r1

15、r2;4.r4=(r3);5.r5,即第一个b;6.r6=(r5)*;7.r7=r4r6;8.r8=(r7);9.r9=(r8)*.得到的正则表达式

16、转NFA为：23bstart01678910a452’.NFA转DFA:NFA状态DFA状态ab0,1,2,3,4,6,7,9,10ABC1,2,3,4,5,6,7,9,10BBC1,2,3,4,6,7,8,9,10CBC用子集法构造得DFA图如下：（４）（ａ｜ｂ）*abb（ａ｜ｂ）*答：对应的NFA如下所示：等价NFA的开始状态A是ε—closure(0)，即A={0，1，2，4，7}由于NAF的输入字母表是{a,b},则Dtran[A,a]=ε-closure(mo

17、ve(A,a))=ε-closure（{3，8}）={1,2,3,4,6,7,8}=BDtran[A,b]=ε-closure(move(A,b))=ε-closure（{5}）={1,2,4,5,6,7}=CDtran[B,a]=ε-closure(move(B,a))=ε-closure（{3，8}）=BDtran[B,b]=ε-closure(move(B,b))=ε-closure（{5，9}）={1,2,4,5,6,7,9}=DDtran[C,a]=ε-closure(move(C,a

18、))=ε-closure（{3，8}）=BDtran[C,b]=ε-closure(move(C,b))=ε-closure（{5}）=CDtran[D,a]=ε-closure(move(D,a))=ε-closure（{3，8}）=BDtran[D,b]=ε-closure(move(D,b))=ε-closure（{5，10}）={1,2,4,5,6,7,10,11,12,13,15,18}=EDtran[E,a]=ε-closure(move(E,a))=ε-closure（{3，8，1