蒋立源编译基本知识第三版第三章知识题与答案解析(修改后)

.第3章习题3-1 试构造一右线性文法，使得它与如下的文法等价S→ABA→UTU→aU|aD→bT|bB→cB|c并根据所得的右线性文法，构造出相应的状态转换图。谢谢阅读3-2 对于如题图3-2所示的状态转换图写出相应的右线性文法；指出它接受的最短输入串；任意列出它接受的另外4个输入串；任意列出它拒绝接受的4个输入串。3-3 对于如下的状态转换矩阵：.分别画出相应的状态转换图；写出相应的3型文法；用自然语言描述它们所识别的输入串的特征。3-4 将如下的NFA确定化和最小化：.3-5 将如题图3-5所示的具有ε动作的NFA确定化。精品文档放心下载.题图3-5 具有ε动作的NFA3-6 设有文法G[S]：S→aAA→aA|bBB→bB|cC|cC→cC|c试用正规式描述它所产生的语言。感谢阅读3-7 分别构造与如下正规式相应的NFA。((0*|1)(1*0))*b|a(aa*b)*b3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应的DFA。感谢阅读.第3章习题答案3-1 解：根据文法知其产生的语言是:L[G]={ambnci|m,n,i≧1}可以构造与原文法等价的右线性文法:S→aAA→aA|bBB→bB|cC|cC→cC|c其状态转换图如下:谢谢阅读3-2(1)

解:其对应的右线性文法是G[A]:A→0D B→0A|1CD→0B|1C E→0B|1C

C→0A|1F|1F→1A|0E|0.最短输入串为011任意接受的四个输入串为：0110,0011,000011,00110谢谢阅读任意拒绝接受的输入串为：0111，1011，1100，1001谢谢阅读3-3 解:(1)相应的状态转换图为：baa,bSaAbB与(ⅰ)相应的状态转换图ba,bSaAaCbBba与(ⅱ)相应的状态转换图.ba,bSaAaBb与(ⅲ)相应的状态转换图ba,bSaAaCbbBa与(ⅳ)相应的状态转换图答案图3-3(2)相应的3型文法为：(ⅰ)S→aA|bS A→aA|bB|b B→aB|bB|a|b谢谢阅读(ⅱ)S→aA|bB|a A→bA|aC|a|b B→aB|bC|b C→aC|bC|a|b谢谢阅读(ⅲ)S→aA|bB|b A→aB|bA|a B→aB|bB|a|b感谢阅读(ⅳ)S→bS|aA A→aC|bB|a B→aB|bC|b C→aC|bC|a|b谢谢阅读(3)用自然语言描述的输入串的特征为：以任意个(包括0个)b开头，中间有任意个（大于1）a，跟一个b，还可以有一个由a,b组成的任意字符串。谢谢阅读以a打头，中间有任意个（包括0个）b,再跟a,最后由一个a,b所组成的任意串结尾；或者以b打头，中间有任意个（包括0个）a,再跟b,最后由一个a,b所组成的任意串结尾。谢谢阅读.以a打头，后跟任意个（包括0个）b，再跟a，最后由一个a,b所组成的任意串结尾；或者以b打头，由一个a,b所组成的任意串结尾。谢谢阅读(ⅳ)以任意个（包括0个）b开头,中间跟aa，最后由一个a,b所组成的任意串结尾；或者以任意个（包括0个）b开头，中间跟ab后，再接任意个（包括0个）a，再接b，最后由一个a,b所组成的任意串结尾。精品文档放心下载3-4 解：将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-(1)之(a)所示，给各状态重新命名，即令：感谢阅读[S]=1, [S,A]=2, [A,B]=3, [B]=4谢谢阅读且由于3及4的组成中均含有M的终态B，故3和4组成了DFAM′的终态集Z′。于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-(1)之(b)及(c)所示。精品文档放心下载.abab[S][S,A]12[S,A][S,A][A,B]223[A,B][B][A,B]343[B][B]44初态:[S]终态:[A,B],[B]初态:1终态:3,4(a)确定化后的状态矩阵(b)改名后的状态矩阵aba1aba423DFAM′的状态转换图答案图3-4-(1)现将DFAM′最小化：(ⅰ)初始分划由两个子集组成，即π0:{1,2},{3,4}(ⅱ)为得到下一分划，考察子集{1,2}。因为{2}b={3}{3,4}但 {1}b=故1和2可区分，于是便得到下一分划π1:{1},{2},{3,4}(ⅲ)又因π1≠π0，再考虑{3,4}，因为{3}b={3}{3,4}而 {4}b=.3和4可区分，从而又得到π2:{1},{2},{3},{4}此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。谢谢阅读将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-(2)之(a)所示，给各状态重新命名，即令：感谢阅读[S]=1, [A]=2, [B,C]=3且由于3的组成中含有M的终态C，故3为DFAM′的终态。于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-(2)之(b)及(c)所示。感谢阅读abab[S][A]12[A][B,C][A]232[B,C][A]32初态:[S]终态:[B,C]初态:1终态:3(a)确定化后的状态矩阵(b)改名后的状态矩阵b1aa32aDFAM′的状态转换图答案图3-4-(2)现将DFAM′最小化：.(ⅰ)初始分划由两个子集组成，即π0:{1,2},{3}(ⅱ)为得到下一分划，考察子集{1,2}。因为{2}b={2}{1,2}但 {1}b=故1和2可区分，于是便得到下一分划π1:{1},{2},{3}此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。谢谢阅读将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-(3)之(a)所示，给各状态重新命名，即令：感谢阅读[S]=1, [A]=2, [S,B]=3且由于3的组成中含有M的终态B，故3为DFAM′的终态。于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-(3)之(b)及(c)所示。感谢阅读.abab[S][A]12[A][S,B]23[S,B][A]32初态:[S]终态:[S,B]初态:1终态:3(a)确定化后的状态矩阵(b)改名后的状态矩阵1ab23aDFAM′的状态转换图答案图3-4-(3)现将DFAM′最小化：(ⅰ)初始分划由两个子集组成，即π0:{1,2},{3}(ⅱ)为得到下一分划，考察子集{1,2}。因为{2}b={3}但 {1}b=故1和2可区分，于是便得到下一分划π1:{1},{2},{3}此时子集已全部分裂，故最小化的过程宣告结束，M′即为状态数最小的DFA。精品文档放心下载将NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-4-(4)之(a)所示，谢谢阅读.给各状态重新命名，即令：[A]=1, [B,C]=2, [B]=3, [C]=4精品文档放心下载且由于2和4的组成中含有M的终态C，故2和4组成了DFAM′的终态集Z′。于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-4-(4)之(b)及(c)所示。精品文档放心下载abab[A][B,C][B]123[B,C][A][C]214[B][A]31[C][A][C]414初态:[A] 终态:[B,C],[C] 初态:1 终态:2,4谢谢阅读(a)确定化后的状态矩阵 (b)改名后的状态矩阵感谢阅读.aabbab3124a(c)DFAM′的状态转换图aa3b1a2b对DFAM′最小化后所得DFAM〞的状态转换图答案图3-4-(4)感谢阅读现将DFAM′最小化：(ⅰ)初始分划由两个子集组成，即π0:{1,3},{2,4}(ⅱ)为得到下一分划，考察子集{1,3}。因为{1}a={2}{2,4}但 {3}a={1}{1,3}故1和3可区分，于是便得到下一分划π1:{1},{3},{2,4}(ⅲ)又因π1≠π0，再考虑{2,4}，因为{2}a={4}a={1}, {2}b={4}b={4}感谢阅读所以2和4不可区分，故子集{S,B}已不能再分裂。此时π2=π1，子集分裂的过程宣告感谢阅读.结束。现选择状态2作为{2,4}的代表，将状态4从状态转换图中删去，并将原来引谢谢阅读4的矢线都引至2，这样，我们就得到了最小化后的DFAM〞如答案图3-4-(4)之(d)谢谢阅读所示。3-5 解：将具有ε动作的NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-5-(1)精品文档放心下载之(a)所示，给各状态重新命名，即令：[S,B,C]=1, [A]=2, [B,C]=3, [C]=4感谢阅读且由于1,3和4的组成中均含有M的终态C，故1,3和4组成了DFAM′的终态集Z′。谢谢阅读于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-5-(1)之(b)及(c)所示。感谢阅读abcabc[S,B,C][A][B,C]123[A][C]24[B,C][B,C]33[C]4初态:[S]终态:[S,B,C],[B,C],[C]初态:1终态:1,3,4(a)确定化后的状态矩阵(b)改名后的状态矩阵c3ca2b41DFAM′的状态转换图答案图3-5-(1).将具有ε动作的NFAM确定化后得DFAM′，其状态转换矩阵如答案图3-5-(2)谢谢阅读之(a)所示，给各状态重新命名，即令：[S]=1, [Z]=2, [R,U]=3, [S,X]=4,谢谢阅读[R,U,Y]=5, [S,U,X]=6, [S,Z]=7, [R,U,Y,Z]=8精品文档放心下载且由于2,7和8的组成中均含有M的终态Z，故2,7和8组成了DFAM′的终态集Z′。谢谢阅读于是，所构造之DFAM′的状态转换矩阵和状态转换图如答案图3-5-(2)之(b)及(c)所示。感谢阅读abab[S][Z][R,U]123[Z]2[R,U][S,X][Z]342[S,X][Z][R,U,Y]425[R,U,Y][S,X,U][Z]562[S,U,X][Z,S][R,U,Y,Z]678[S,Z][Z][R,U]723[R,U,Y,Z][S,X,U][Z]862初态:[S]终态:[Z],[S,Z],[R,U,Y,Z]初态:1终态:2,7,8(a)确定化后的状态矩阵(b)改名后的状态矩阵.1b3b7aaab4b5a6b8aba2baDFAM′的状态转换图答案图3-5-(2)3-6解：首先将文法写成方程组：S=aA(1)A=aA+bB(2)B=bB+cC+c(3)C=cC+c(4)将(4)代入(3)，得：B=bB+C(5)由论断3.1，方程(4)的解为:C=c*c将上式代入(5)，得：.B=bB+c*c由论断3.1，得：B=b*c*c将上式代入(2)，得：A=aA+b*bc*c由论断3.1，得：A=a*b*bc*c将上式代入(1)，得：S=a*ab*bc*c即文法所产生的语言可用正规式a*ab*bc*c表示。谢谢阅读3-7 解：(1)构造与正规式((0*|1)(1*0))*相应的NFA的步骤如答案图3-7-(1)所示：感谢阅读.(0*|1)(1*0)Sε1εS0f21*00*|1Sε1εS0f1*2310*0Sε1εS0fε 2ε1 5ε1403ε0Sε1ε0答案图3-7-(1) 正规式((0*|1)(1*0))*的NFA精品文档放心下载

Sf(2)构造与正规式b|a(aa*b)*b相应的NFA的步骤如答案图3-7-(2)所示：谢谢阅读.a(aa*b)*bSS0fba(aa*b)*bS12S0fbaa*bSa1ε3ε2bS0fba*54ababS1ε3ε2S0fbaε6ε54ababS1ε3ε2S0fb答案图3-7-(2) 正规式b|a(aa*b)*b的NFA感谢阅读.3-8 解：首先，构造与正规式(a|b)*(aa|bb)(a|b)*相应的NFAM，其构造步骤如答案图3-8(a)谢谢阅读所示：S(a|b)*1aa|bb2(a|b)*Za|baaa|bSε3ε12ε4εZbbaa5aaSε3ε12ε4εZbb6bb答案图3-8(a)正规式(a|b)*(aa|bb)(a|b)*的NFAM其次，将答案图3-8(a)所示的具有ε动作的NFAM确定化后得到DFAM′，其状态感谢阅读转换矩阵如答案图3-8(b)所示，给各状态重新命名，即令：[S,3,1]=S,[3,1,5]=A,[3,1,6]=B,[3,1,5,2,4,Z]=C,[3,1,6,2,4,Z]=D,[3,1,6,4,Z]=E,[3,1,5,4,Z]=F且由于C,D,E和F的组成中均含有NFAM的终态Z，故C,D,E和F组成了DFAM′的终态集Z′。于是，将NFAM确定化后所得DFAM′的状态转换矩阵和状态转换图如答案感谢阅读3-8(c)及(d)所示。.ab[S,3,1][3,1,5][3,1,6][3,1,5][3,1,5,2,4,Z][3,1,6][3,1,6][3,1,5][3,1,6,2,4,Z][3,1,5,2,4,Z][3,1,5,2,4,Z][3,1,6,4,Z][3,1,6,2,4,Z][3,1,5,4,Z][3,1,6,2,4,Z][3,1,6,4,Z][3,1,5,4,Z][3,1,6,2,4,Z][3,1,5,4,Z][3,1,5,2,4,Z][3,1,6,4,Z]初态:[S,3,1]终态:[3,1,5,2,4,Z],[3,1,6,2,4,Z],[3,1,6,4,Z],[3,1,5,4,Z]感谢阅读(b)确定化后的状态矩阵aAaCaSabbBDbb

abSABACBBADCCEDFDEFDFCE初态:S终态:C,D,E,F(c)改名后的状态矩阵bEbb aaFaDFAM′的状态转换图aAaSaba,bCbBb对DFAM′最小化后所得的DFAM〞的状态转换图感谢阅读.答案