第三章答案.doc

第三章习题解答Aho：编译原理书中习题陈：程序设计语言编译原理书中习题(Aho)3.6 描述下列正规式定义的语言a) 0(0 | 1)*0解：定义的语言L=以0开头、以0结尾的0、1串b) (e | 0)1*)*解：定义的语言L=所有0、1串c) (0 | 1)*0(0 | 1)(0 | 1)解：定义的语言L=第3位为0的二进制串d) 0*10*10*10*解：定义的语言L=包含3个1的0、1串e) (00 | 11)*(01 | 10)(00 | 11)*(01 | 10)(00 | 11)*)*解：定义的语言L=包含偶数个0、偶数个1的0、1串首先画出正规式对应的NFA：将它转换为DFAe-closure(0) = 0, 3, 14 = Ae-closure(d(0, 3, 14, 0) = 1, 4, 12 = Be-closure(d(0, 3, 14, 1) = 2, 5, 13 = Ce-closure(d(1, 4, 12, 0) = Ae-closure(d(1, 4, 12, 1) = 6, 9 = De-closure(d(2, 5, 13, 0) = De-closure(d(2, 5, 13, 1) = Ae-closure(d(6, 9, 0) = 7, 10 = Ee-closure(d(6, 9, 1) = 8, 11 = Fe-closure(d(7, 10, 0) = De-closure(d(7, 10, 1) = 3, 14 = Ge-closure(d(8, 11, 0) = Ge-closure(d(8, 11, 1) = D e-closure(d(3, 14, 0) = 4, 12 = He-closure(d(3, 14, 1) = 5, 13 = Ie-closure(d(4, 12, 0) = Ge-closure(d(4, 12, 1) = De-closure(d(5, 13, 0) = De-closure(d(5, 13, 1) = G对此DFA进行化简：01. B, C, D ,E, F, H, I, A, G12. B, C, D, E, F, H, IB, F, H, C, D, E, IA, G3. C, D, E, IC, E, I, DB, F, H, A, GA：偶数个0，偶数个1的0、1串B：奇数个0，偶数个1的0、1串C：偶数个0，奇数个1的0、1串D：奇数个0，奇数个1的0、1串(Aho)3.7 为下列语言写出正规定义（或正规式、正规文法、有限自动机）a) 包含五个元音，且按顺序排列的所有字母串解：conb-df-hj-np-tv-zstring(con)*a(con | a)*(con)*e(con | e)*(con)*i(con | i)*(con)*o(con | o)* (con)*u(con | u)*b) 字母按字典升序排列的所有字母串解：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*c) 以/*开始，*/结束的注释，中间不能包含*/，除非包含在和中解：/*(* | .* | *+/)*/其中，/*和*/间出现内容，是三种不同情况的闭包（随意组合出的任意长度的串）*：除了*和之外所有的符号任意长度的串.*：两个引号括起来的串，其内允许任何符号*+/：出现*的情况，其后跟一个不是/的符号，这主要是避免*后接*，产生*/的情况，至于后面跟随多个不是/的符号，第一个之后的内容可与*匹配但还遗漏了一种情况，即*后不跟随任何符号的情况，即立即接注释结尾的*/的情况，这只需在*/之前加一个*即可，有这种情况，与之匹配；没有e，也匹配d) 不包含重复数字的数字串解：09十个数字的情况比较复杂，考虑只有02三个数字的情况，对应DFA为状态含义：s：e0：最后一个符号为0的数字串1：最后一个符号为1的数字串2：最后一个符号为2的数字串3：死状态e) 包含至多一个重复数字的数字串解：同样可给出DFA，按d)类似方法设计状态即可f) 包含偶数个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”h) 不包含子串011的0、1串解：DFA为状态0：字符串未包含0状态1：字符串包含子串0状态2：字符串包含子串01状态3：字符串包含子串011正规式为：1*0* | 1*00*1(00*1)* = 1*(0 | 01)*i) 不包含子序列011的0、1串解：DFA为状态0：字符串未包含0状态1：字符串包含子序列0状态2：字符串包含子序列01状态3：字符串包含子序列011正规式为：1* | 1*00* | 1*00*10*(Aho)3.14 用正规式表示UNIX的文件名表达式解：只需将文件名表达式允许的所有操作符用正规式表示出来即可s“s”cc*.*?.ss(Aho)3.16 使用Thompson构造法为下列正规式构造NFA，写出每个NFA处理符号串ababbab过程中的状态转换序列a) (a | b)*解：NFA为ababbab状态转换序列：012461356124613561356124613567b) (a* | b*)*解：NFA为ababbab状态转换序列：01246810135791012468101357579101246810135791011c) (e | a)b*)*解：NFA为ababbab状态转换序列：01356789135678789135678910d) (a | b)*abb(a | b)*解：NFA为ababbab状态转换序列：01246135678910111214161113151617(Aho)3.17 利用子集构造法将3.16题得到的NFA转换为DFA，同样写出分析符号串ababbab过程中的状态转换。a) 解：e-closure(0) = 0, 1, 2, 3, 7 = Ae-closure(d(A, a) = 1, 2, 3, 4, 6, 7 = Be-closure(d(A, b) = 1, 2, 3, 5, 6, 7 = Ce-closure(d(B, a) = Be-closure(d(B, b) = Ce-closure(d(C, a) = Be-closure(d(C, b) = Cababbab状态转换序列：ABCBCCBCb) 解：e-closure(0) = 0, 1, 2, 3, 4, 5, 8, 9, 10, 11 = Ae-closure(d(A, a) = 1, 2, 3, 4, 5, 6, 8, 9, 10, 11 = Be-closure(d(A, b) = 1, 2, 3, 4, 5, 7, 8, 9, 10, 11 = Ce-closure(d(B, a) = Be-closure(d(B, b) = Ce-closure(d(C, a) = Be-closure(d(C, b) = Cababbab状态转换序列：ABCBCCBCc) 解：e-closure(0) = 0, 1, 2, 3, 4, 6, 7, 9, 10 = Ae-closure(d(A, a) = 1, 2, 3, 4, 5, 6, 7, 9, 10 = Be-closure(d(A, b) = 1, 2, 3, 4, 6, 7, 8, 9, 10 = Ce-closure(d(B, a) = Be-closure(d(B, b) = Ce-closure(d(C, a) = Be-closure(d(C, b) = Cababbab状态转换序列：ABCBCCBCd) 解：e-closure(0) = 0, 1, 2, 3, 7 = Ae-closure(d(A, a) = 1, 2, 3, 4, 6, 7, 8 = Be-closure(d(A, b) = 1, 2, 3, 5, 6, 7 = Ce-closure(d(B, a) = Be-closure(d(B, b) = 1, 2, 3, 5, 6, 7, 9 = De-closure(d(C, a) = Be-closure(d(C, b) = Ce-closure(d(D, a) = Be-closure(d(D, b) = 1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 17 = Ee-closure(d(E, a) = 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 17 = Fe-closure(d(E, b) = 1, 2, 3, 5, 6, 7, 11, 12, 13, 15, 16, 17 = Ge-closure(d(F, a) = Fe-closure(d(F, b) = 1, 2, 3, 5, 6, 7, 9, 11, 12, 13, 15, 16, 17 = He-closure(d(G, a) = Fe-closure(d(G, b) = Ge-closure(d(H, a) = Fe-closure(d(H, b) = 1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 15, 16, 17 = Ie-closure(d(I, a) = Fe-closure(d(I, b) = Gababbab状态转换序列：ABDBDEFH(Aho)3.18 为3.16的正规式直接构造DFA，比较得到结果与3.17结果的状态数。a) 解：followpos11, 2, 321, 2, 33firstpos(root) = 1, 2, 3 = Ad(A, a) = followpos(1) = 1, 2, 3 = Ad(A, b) = followpos(1) = 1, 2, 3 = Ab) 解：followpos11, 2, 321, 2, 33firstpos(root) = 1, 2, 3 = Ad(A, a) = followpos(1) = 1, 2, 3 = Ad(A, b) = followpos(1) = 1, 2, 3 = Ac) 解：followpos11, 2, 321, 2, 33firstpos(root) = 1, 2, 3 = Ad(A, a) = followpos(1) = 1, 2, 3 = Ad(A, b) = followpos(1) = 1, 2, 3 = Ad) 解：followpos11, 2, 321, 2, 3344556, 7, 866, 7, 876, 7, 88firstpos(root) = 1, 2, 3 = Ad(A, a) = followpos(1)followpos(3) = 1, 2, 3, 4 = Bd(A, b) = followpos(2) = Ad(B, a) = followpos(1)followpos(3) = Bd(B, b) = followpos(2)followpos(4) = 1, 2, 3, 5 = Cd(C, a) = followpos(1)followpos(3) = Bd(C, b) = followpos(2)followpos(5) = 1, 2, 3, 6, 7, 8 = Dd(D, a) = followpos(1)followpos(3)followpos(6) = 1, 2, 3, 4, 6, 7, 8 = Ed(D, b) = followpos(2)followpos(7) = Dd(E, a) = followpos(1)followpos(3)followpos(6) = Ed(E, b) = followpos(2)followpos(4)followpos(7) = 1, 2, 3, 5, 6, 7, 8 = Fd(F, a) = followpos(1)followpos(3)followpos(6) = Ed(A, b) = followpos(2)followpos(7) = D(Aho)3.21 最小化3.18得到的DFAd) 解：b初始划分：A, B, C, D, E, FbA, B, CA, B, CA, BA, B3.22 正规式的等价可以通过对应的最小化的DFA的结构等价性来证明，利用这种方法，证明下列正规式的等价性a) (a | b)*b) (a* | b*)*c) (e | a)b*)*由16、17、18、21结果可知（陈）7 构造下列正规式对应的DFA解法：可正规式NFADFA，或者正规式DFAa) 1(0 | 1)*101b) 1(1010* | 1(010)*1)*0c) 0*10*10*10*d) (00 | 11)*(01 | 10)(00 | 11)*(01 | 10)(00 | 11)*)*（陈）8 为下列语言写出正规定义（或正规式、正规文法、有限自动机）a) 以01结尾的0、1串解：(0 | 1)*01b) 能被5整除的十进制整数解：1-90-9*(0 | 5) | 0 | 5c) 包含奇数个1和奇数个0的二进制串解：(00 | 11)*(01 | 10)(01 | 10)+(00 | 11)*(01 | 10)+)*解法见Aho3.7f（陈）10 一个人带一只狼、一只羊和一颗白菜过河，每次人只能将一样东西摆渡到对岸。而在无人的情况下，狼会吃掉羊，羊会吃掉白菜。目标，人将三样东西都摆渡到对岸，羊和白菜都不被吃掉。利用有限自动机得到渡河的方法解：M人，W狼，S羊，C白菜，状态哪些东西在原岸，如：MWS，表示人、狼、羊在原岸（白菜在目的岸）动作人将一样东西摆渡到对岸（原目的表示为，也可能是目的原表示为）不满足要求的状态为死状态，如：WS、SC、初态：MWSC，终态：e，初态到终态的一条路径渡河方案。d(MWSC, MW) = SC（红色表示死状态）d(MWSC, MS) = WCd(MWSC, MC) = WSd(MWSC, M) = WSCd(WC, MW) = MWSC（蓝色表示出现过的状态）d(WC, M) = MWCd(WSC, M) = MWSCd(MWC, MW) = Cd(MWC, MC) = Wd(MWC, M) = WCd(C, MW) = MWCd(C, MS) = MSCd(C, M) = MCd(W, MS) = MWSd(W, MC) = MWCd(W, M) = MWd(MSC, MS) = Cd(MSC, MC) = Sd(MSC, M) = SCd(MWS, MW) = Sd(MWS, MS) = Wd(MWS, M) = WSd(S, MW) = MWSd(S, MC) = MSCd(S, M) = MSd(MS, MS) = e终态！d(MS, M) = S状态转换序列：MWSCWCMWCCMSCSMSe动作序列：MS，M，MW，MS，MC，M，MS（陈）12 将下面DFA最小化解：初始划分：0, 1, 2, 3, 4, 5a2, 3, 4, 52, 4, 3, 5（陈）14 构造DFA，它接受S=0, 1上所有满足如下条件的符号串：每个1都有0直接跟在右边。（陈）17 下面符号串集合是否为正规集？若是，写出正规式，否则，给出证明a) L1 = anbn | n = 0解：不是正规集，证明见讲义4-1第51页b) L2 = x | x中含有相同个数的a和b解：不是正规集，证明类似a)c) L3 = ap | p为素数解：不是正规集证明：假设L3是正规集，对应DFA D的状态数为k。令p0、p1、pk为前k+1个素数，s0、s1、sk为D读入ap0、ap1、apk后到达的状态。显然，必有0=ij 1，因此pi * (pj - pi + 1)为合数。D接受t，但t不是L3中符号串，矛盾。因此，L3不是正规集。