DOC《第三章习题解答》

第三章习题解答 Aho:《编译原理》书中习题 陈:《程序设计语言编译原理》书中习题 (Aho)3.

6 描述下列正规式定义的语言 0(0 | 1)*0 解:定义的语言L={以0开头、以0结尾的

0、1串} ((? | 0)1*)* 解:定义的语言L={所有

0、1串} (0 | 1)*0(0 | 1)(0 | 1) 解:定义的语言L={第3位为0的二进制串} 0*10*10*10* 解:定义的语言L={包含3个1的

0、1串} (00 | 11)*((01 | 10)(00 | 11)*(01 | 10)(00 | 11)*)* 解:定义的语言L={包含偶数个

0、偶数个1的

0、1串} 首先画出正规式对应的NFA: 将它转换为DFA ?-closure({0}) = { 0, 3, 14} = A ?-closure(?({0, 3, 14}, 0)) = {1, 4, 12} = B ?-closure(?({0, 3, 14}, 1)) = {2, 5, 13} = C ?-closure(?({1, 4, 12}, 0)) = A ?-closure(?({1, 4, 12}, 1)) = {6, 9} = D ?-closure(?({2, 5, 13}, 0)) = D ?-closure(?({2, 5, 13}, 1)) = A ?-closure(?({6, 9}, 0)) = {7, 10} = E ?-closure(?({6, 9}, 1)) = {8, 11} = F ?-closure(?({7, 10}, 0)) = D ?-closure(?({7, 10}, 1)) = {3, 14} = G ?-closure(?({8, 11}, 0)) = G ?-closure(?({8, 11}, 1)) = D ?-closure(?({3, 14}, 0)) = {4, 12} = H ?-closure(?({3, 14}, 1)) = {5, 13} = I ?-closure(?({4, 12}, 0)) = G ?-closure(?({4, 12}, 1)) = D ?-closure(?({5, 13}, 0)) = D ?-closure(?({5, 13}, 1)) = G 对此DFA进行化简: 1. {B, C, D ,E, F, H, I}, {A, G} 2. {B, C, D, E, F, H, I}――{B, F, H}, {C, D, E, I} {A, G} 3. {C, D, E, I}――{C, E, I}, {D} {B, F, H}, {A, G} A:偶数个0,偶数个1的

0、1串B:奇数个0,偶数个1的

0、1串C:偶数个0,奇数个1的

0、1串D:奇数个0,奇数个1的

0、1串(Aho)3.7 为下列语言写出正规定义(或正规式、正规文法、有限自动机) 包含五个元音,且按顺序排列的所有字母串 解:con→[b-df-hj-np-tv-z] string→(con)*a(con | a)*(con)*e(con | e)*(con)*i(con | i)*(con)*o(con | o)* (con)*u(con | u)* 字母按字典升序排列的所有字母串 解:a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z* 以/*开始,*/结束的注释,中间不能包含*/,除非包含在 和 中解: 其中,/*和*/间出现内容,是三种不同情况的闭包(随意组合出的任意长度的串) [^* ]*:除了*和 之外所有的符号任意长度的串 .* :两个引号括起来的串,其内允许任何符号 *+[^/]:出现*的情况,其后跟一个不是/的符号,这主要是避免*后接[^* ]*,产生*/的情况,至于后面跟随多个不是/的符号,第一个之后的内容可与[^* ]*匹配 但还遗漏了一种情况,即*后不跟随任何符号的情况,即立即接注释结尾的*/的情况,这只需在*/之前加一个**即可,有这种情况,与之匹配;

没有――?,也匹配 不包含重复数字的数字串 解:0-9十个数字的情况比较复杂,考虑只有0-2三个数字的情况,对应DFA为 状态含义: s:? 0:最后一个符号为0的数字串 1:最后一个符号为1的数字串 2:最后一个符号为2的数字串 3:死状态 包含至多一个重复数字的数字串 解: 同样可给出DFA,按d)类似方法设计状态即可 包含偶数个0和奇数个1的

0、1串解:DFA为 状态含义与上题3.6 e)相同. 正规式为AB*,其中 A =

1 | 0(00 | 11)*(10 | 01) B =

00 |

11 | (01 | 10)(00 | 11)*(01 | 10) DFA(正规式的转换方法见参考资料 NFA to RegEx Conversion.htm 不包含子串011的

0、1串解:DFA为 状态0:字符串未包含0 状态1:字符串包含子串0 状态2:字符串包含子串01 状态3:字符串包含子串011 正规式为:1*0* | 1*00*1(00*1)* = 1*(0 | 01)* 不包含子序列011的

0、1串解:DFA为 状态0:字符串未包含0 状态1:字符串包含子序列0 状态2:字符串包含子序列01 状态3:字符串包含子序列011 正规式为:1* | 1*00* | 1*00*10* (Aho)3.14 用正规式表示UNIX的文件名表达式 解:只需将文件名表达式允许的所有操作符用正规式表示出来即可 '