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

编译原理第 2版参考 习题 有理数乘除混合运算习题护理管理学习题以及答案高等数学极限习题过敏性休克习题与答案诫子书习题及答案 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 （3 章） 第 3章 词法分析 3.2.2 试描述下列正则 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式定义的语言 (1) a( a|b )*a 答: { aa, aaa, aba, aaaa, aaba, abaa, abba, ... },（按穷举法） 或以 a开头和结尾，长度大于等于 2的 a,b 串 （自然语言描述） （2） （（ε|a)b*））* 答: 由 a和 b组成的任意符号串 （3）（a|b）* a(a|b)(a|b) 答: 倒数第 3个符号为 a的长度大于等于 3的 a,b 串 （4）a*ba*ba*ba* 答: 有且仅有三个 b的由 a 和 b 构成的所有串的集合。 3.2.5 : 试写出下列语言的正则定义： （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 为除五元音外的小写字母，记号 ctnvowels 对应的定义即为题目 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 的正则 定义。 (2) 所有由按字典顺序递增序排列的小写字组成的串。 a*b*……z* （3)注释，即/*和*/之间的串，且串中没有不在双引号（“）中的*/。 head——>/* tail ——>*/ incomment->(~(*/)|“.*”) * comment->head incomment tail （9）所有由 a和 b 组成且不含有子串 abb 的串。 A->b*(a︱ab)* 3.3.1 给出 3.2.2 中正则表达式所描述的语言的状态转换图。 (1)a( a|b )*a 的状态转换图如下： （2） （3） start a b a 1 a b 3 2 a 4 5 6 7 b b a 0 （4）a*ba*ba*ba* ε a b ε b b b 3．6.3 使用算法 3.25 和 3.20 将下列正则表达式转换成 DFA： (1) a a a a (2)将（a*|b*）*转换成 DFA NFA： 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)={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）（（ |a）b*）* 解：1’按以下步骤： 1. 子表达式 r1，即表达式 ; 2. r2,即第一个 a; 3. r3 =r1 | r2; 4. r4=(r3); 5. r5, 即第一个 b; 6. r6=(r5)*; 7. r7=r4 r6; 8. r8=(r7); 9. r9=(r8)*. 得到的正则表达式转 NFA 为： start 0  1   a b 2 54 3   6 987   10    2’.NFA 转 DFA: 用子集法构造得 DFA 图如下： NFA 状态 DFA 状态 ba 0,1,2,3,4,6,7,9,10 A B C 1,2,3,4,5,6,7,9,10 B B C 1,2,3,4,6,7,8,9,10 C B C （４）（ａ｜ｂ）*abb（ａ｜ｂ）* 答：对应的 NFA 如下所示： 等价 NFA 的开始状态 A是ε—closure(0)，即 A={0，1，2，4，7} 由于 NAF 的输入字母表是{a,b},则 Dtran[A,a]=ε-closure(move(A,a))= ε-closure（{3，8}）={1,2,3,4,6,7,8}=B Dtran[A,b]= ε-closure(move(A,b))= ε-closure（{5}）={1,2,4,5,6,7}=C Dtran[B,a]= ε-closure(move(B,a))= ε-closure（{3，8}）=B Dtran[B,b]=ε-closure(move(B,b))= ε-closure（{5，9}）={1,2,4,5,6,7,9}=D Dtran[C,a]=ε-closure(move(C,a))= ε-closure（{3，8}）=B Dtran[C,b] =ε-closure(move(C,b))= ε-closure（{5}）=C Dtran[D,a]=ε-closure(move(D,a))= ε-closure（{3，8}）=B Dtran[D,b]=ε-closure(move(D,b))=ε-closure（{5，10}） ={1,2,4,5,6,7,10,11,12,13,15,18}=E Dtran[E,a]=ε-closure(move(E,a))=ε-closure（{3，8，14}） ={1,2,3,4,6,7,8,12,13,14,15,17,18}=F Dtran[E,b] = ε -closure(move(E,b))= ε -closure （ {5,16} ） ={1,2,4,5,6,7, 12,13,15,16,17,18}=G Dtran[F,a]=ε-closure(move(F,a))= ε-closure（{3，8，14}）=F Dtran[F,b] = ε -closure(move(F,b))= ε -closure （ {5,9,16} ） ={1,2,4,5,6,7, 9,12,13,15,16,17,18}=H Dtran[G,a]=ε-closure(move(G,a))= ε-closure（{3，8，14}）=F Dtran[G,b] =ε-closure(move(G,b))= ε-closure（{5, 16}）=G Dtran[H,a]=ε-closure(move(H,a))= ε-closure（{3，8，14}）=F Dtran[H,b] = ε -closure(move(H,b))= ε -closure （ {5,10,16} ） ={1,2,4,5,6,7, 10,11,12,13,15,16,17,18}=I Dtran[I,a]=ε-closure(move(I,a))= ε-closure（{3，8，14}）=F Dtran[I,b] =ε-closure(move(I,b))= ε-closure（{5, 16}）=G DFA D 的转换表 Dtran NFA 状态 DFA 状态 a b {0,1,2,4,7} A B C {1,2,3,4,6,7,8} B B D {1,2,4,5,6,7} C B C {1,2,4,5,6,7,9} D B E {1,2,4,5,6,7,10,11,12,13,15} E F G {1,2,3,4,6,7,8,12,13,14,15,17,18} F F H {1,2,4,5,6,7, 12,13,15,16,17,18} G F G {1,2,4,5,6,7, 9,12,13,15,16,17,18} H F I {1,2,4,5,6,7, 10,11,12,13,15,16,17,18} I F G 可得 DFA 的如下状态转换图：