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

1、第3章习题3-1试构造一右线性文法，使得它与如下的文法等价U f aU|aD f bT|b B f cB|c并根据所得的右线性文法，构造出相应的状态转换图。3-2 对于如题图3-2所示的状态转换图b写出相应的右线性文法;指出它接受的最短输入串;任意列出它接受的另外 4个输入串;任意列出它拒绝接受的 4个输入串。3-3对于如下的状态转换矩阵:分别画出相应的状态转换图;写出相应的3型文法;用自然语言描述它们所识别的输入串的特征。3-4将如下的NFA确定化和最小化:bB繰图:H3-5 将如题图3-5所示的具有动作的NFA确定化。题图3-5具有动作的NFA3-6设有文法GS:A f aA|bBB f

2、bB|cC|cCf cC|c试用正规式描述它所产生的语言。3-7分别构造与如下正规式相应的NFA。3-8构造与正规式(a|b) *(aa|bb)(a|b) *相应的DFA。(1) (0 |1)(1 0) b|a(aa *b)*b第3章习题答案3-1 解：根据文法知其产生的语言是LG=a mbnci| m,n,i i=1可以构造与原文法等价的右线性文法A f aA|bBB f bB|cC|cCf cC|c其状态转换图如下：3-2 解:(1)其对应的右线性文法是GA:A f ODBf 0A|1CCf 0A|1F|1Df 0B|1CEf 0B|1CFf 1A|0E|0最短输入串为011任意接受的四个

3、输入串为:0110,0011,000011,00110任意拒绝接受的输入串为:0111 , 1011 , 1100 , 10013-3解:(1)相应的状态转换图为:baa, b与（i ）相应的状态转换图a, b与（iii）相应的状态转换图（2）相应的3型文法为:(i ) Sf aA|bSA f aA|bB|bB f aB|bB|a|b(ii) Sf aA|bB|aAf bA|aC|a|bB f aB|bC|bCf aC|bC|a|b(iii) S f aA|bB|bA f aB|bA|aBf aB|bB|a|b(iv) S f bS|aAA f aC|bB|aB f aB|bC|bCf aC|

4、bC|a|b（3）用自然语言描述的输入串的特征为:a，跟一个b，还可以有（i ）以任意个（包括0个）b开头，中间有任意个（大于 1）一个由a,b组成的任意字符串。（ii）以a打头，中间有任意个（包括 0个）b,再跟a,最后由一个a,b所组成的任意串结尾；或者以b打头，中间有任意个（包括 0个）a,再跟b,最后由一个a,b所组成的任意串结尾。(iii)以a打头，后跟任意个(包括 0个)b ,再跟a,最后由一个a,b所组成的任 意串结尾；或者以 b 打头，由一个 a,b 所组成的任意串结尾。(iv )以任意个(包括尾；或者以任意个(包括再接 b,最后由一个 a,b所组成的任意串结尾。3-4解：0个

5、)b开头冲间跟aa，最后由一个a,b所组成的任意串结 0 个) b 开头,中间跟 ab 后,再接任意个(包括 0 个) a,(1)将NFA M确定化后得DFA M ，其状态转换矩阵如答案图3-4-(1)之(a)所示,给各状态重新命名,即令：S=1,S,A=2,A,B=3,B=4且由于3及4的组成中均含有 M的终态B,故3和4组成了 DFA M 的终态集Z 于是，所构造之DFA M 的状态转换矩阵和状态转换图如答案图3-4-(1)之(b)及(c)所示。SS,AS,AS,AA,BA,BBA,BBB初态:S终态：A,B,B初态:1终态:3,4答案图34(1)现将DFA M 最小化:(i )初始分划由

6、两个子集组成，即(ii )为得到下一分划，考察子集1,2。因为2b =33,4 1b =和2可区分，于是便得到下一分划n: 1, 2, 3,4(iii)又因n1工n，再考虑3,4，因为3b =33,4 4b =故3和4可区分，从而又得到n: 1, 2, 3, 4此时子集已全部分裂，故最小化的过程宣告结束，M 即为状态数最小的DFA。将NFA M确定化后得DFA M ，其状态转换矩阵如答案图3-4-(2)之(a)所示, 给各状态重新命名，即令:S=1,A=2,B,C=3且由于3的组成中含有 M的终态C,故3为DFA M 的终态。于是，所构造之DFA M 的状态转换矩阵和状态转换图如答案图34(2

7、)之(b)及(c)所示。终态:3(c) DFA M 的状态转换图ababSA12A E,CA232B,CA32初态：S 终态:B,C初态:1答案图3-4-(2)现将DFA M 最小化:(i )初始分划由两个子集组成，即n:1,2, 3(ii )为得到下一分划，考察子集1,2。因为2b =2 1,2 1b故1 和2可区分，于是便得到下一分划n： 1, 2, 3此时子集已全部分裂，故最小化的过程宣告结束，M 即为状态数最小的DFA。将NFA M确定化后得DFA M ，其状态转换矩阵如答案图3-4-(3)之(a)所示, 给各状态重新命名，即令：S=1,A=2,S,B=3且由于3的组成中含有 M的终态

8、B,故3为DFA M 的终态。于是，所构造之DFA M 的状态转换矩阵和状态转换图如答案图3-4-(3)之(b)及(c)所示。ababSA12AS,B23S,BA32初态：S 终态：S,B初态:1 终态:3(a) 确定化后的状态矩阵(b) 改名后的状态矩阵a(c) DFA M 的状态转换图答案图3-4-(3)现将DFA M 最小化:(i )初始分划由两个子集组成，即(ii )为得到下一分划，考察子集1,2。因为2b =3 1b =故1和2可区分，于是便得到下一分划n： 1, 2, 3此时子集已全部分裂，故最小化的过程宣告结束，M 即为状态数最小的DFA。将NFA M确定化后得DFA M ，其状

9、态转换矩阵如答案图3-4-(4)之(a)所示,给各状态重新命名，即令:A=1,B,C=2,B=3,C=4所构造之DFA M且由于2和4的组成中含有 M的终态C,故2和4组成了 DFA M 的终态集Z。于是,的状态转换矩阵和状态转换图如答案图3-4-(4)之(b)及(C)所示。(a) 确定化后的状态矩阵(b) 改名后的状态矩阵ababAB,CB123B,CAC214BA3 1CAC414初态:A1终态:B,C,C初态:1 终态:2,4aaba(c) DFA M 的状态转换图(d) 对DFA M最小化后所得DFA M的状态转换图答案图3-4-(4)现将DFA M 最小化:(i )初始分划由两个子集

10、组成，即(ii )为得到下一分划，考察子集1,3。因为1a =22,4 3a =1 1,3故1和3可区分，于是便得到下一分划n: 1, 3, 2,4(iii)又因n1工n，再考虑2,4，因为2a =4 a =1,2b =4 b =4所以2和4不可区分，故子集S,B已不能再分裂。此时n 2 = n1 ,子集分裂的过程宣告结束。(iv )现选择状态2作为2,4的代表，将状态4从状态转换图中删去，并将原来引至4的矢线都引至2，这样，我们就得到了最小化后的DFA M 如答案图3-4-(4)之(d)所示。3-5 解:(1)将具有动作的NFA M确定化后得DFA M 其状态转换矩阵如答案图3-5-(1)之

11、(a)所示，给各状态重新命名，即令:S,B,C=1,A=2,B,C =3,C=4且由于1,3和4的组成中均含有 M的终态C,故1,3和4组成了 DFA M 的终态集Z 。于是，所构造之DFA M 的状态转换矩阵和状态转换图如答案图3-5-(1)之(b)及(c)所示。abca b cS,B,CAB,C1AC24B,CB,C3C42初态:S终态：S,B,C,B,C,C初态:1 终态:1,3,4(a) 确定化后的状态矩阵(b) 改名后的状态矩阵(c) DFA M 的状态转换图答案图3-5-(1)(2)将具有动作的NFA M确定化后得DFA M 其状态转换矩阵如答案图 3-5-(2)之(a)所示，给各

12、状态重新命名，即令: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组成了 DFA M 的终态集Z 。于是，所构造之DFA M 的状态转换矩阵和状态转换图如答案图3-5-(2)之(b)及(c)所示。SZR,UZR,US,XR,U, YS,U,XS,ZR,U, YZ初态:S,XZZSXUZ,SR,U, YZR,U, YZZR,US,X,UZ终态:Z,S,Z,R,U,YZ初态:终态:2,7,8确定化后的状态矩阵(b)改名后的状态矩阵答案图3-5-(2)3-6 解:首先将文法写成方程组

13、:(1)S=aAA=aA+bBB=bB+cC+cC=cC+c将代入，得:(5)B=bB+C由论断3.1，方程的解为:C=c*c将上式代入(5)，得:由论断 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) 所示：S(0*|1) (1*0)答案图 3-7-(1) 正规式(0*1

14、1 ) ( 1* 0 ) )* 的NFA构造与正规式 b|a(aa*b)*b相应的NFA的步骤如答案图3-7-(2)所示:答案图3-7-(2) 正规式b|a(aa *b) *b的NFA3-8 解:首先，构造与正规式(a|b) *(aa|bb)(a|b) *相应的NFA M，其构造步骤如答案图3-8(a)所示:S-0 (a|b)0 aa|bb3aabb2(a|b)*MBb3aa56bbJ 4a答案图3-8 (a)正规式(a|b) (aa|bb)(a|b) 的 NFA M其次，将答案图3-8(a)所示的具有动作的NFA M确定化后得到DFA M 其状态转换矩阵如答案图3-8(b)所示，给各状态重新

15、命名，即令:S,3,1=S,3,1,5=A,3,1,6 =B,3,1,524Z=C,3,1,624,Z=D,3,1,6,4,Z=E,3,1,5,4,Z=F且由于C,D,E和F的组成中均含有 NFA M 的终态 乙故C,D,E和F组成了 DFA M 的终 态集Z 。于是，将NFA M确定化后所得DFA M 的状态转换矩阵和状态转换图如答案 图3-8(c)及(d)所示。aba bS,3,13,1,53,1,6SAB3,1,53,1,5,2,4,Z3,1,6a C B3,1,63,1,53,1,6,2,4,ZB A D3,1,5,2,4,Z3,1,5,2,4,Z3,1,6,4,ZCCE3,1,6,2

16、,4,Z3,1,5,4,Z3,1,6,2,4,ZDFD3,1,6,4,Z3,1,5,4,Z3,1,6,2,4,ZEFD3,1,5,4,Z3,1,5,2,4,Z3,1,6,4,ZFCE初态:S,3,1终态:3,1,5,2,4,Z,初态:S终态：C,D,E,F(b)确定化后的状态矩阵(C)改名后的状态矩阵abBAabbaabab(d)DFA M 的状态转换图3,1,624Z,3,164Z,3,1,5,4Z答案图 3-8最后，将所得DFA M 最小化:(i )初始分划由两个子集组成，即n:S,A,B, C,D,E,F(ii )为得到下一分划，考察子集S,A,B。因为S,Ba =AS,A,B Aa =C C,D,E,F故S,B和A可区分，于是便得到下一分划n: S,B, A, C,D,E,F(iii)因ni工n，考虑S,B，因为Sb =B S,BBb =DC,D,E,F故 S 和 B 可区分，于是便得到下一分划n： S, B, A, C,D,E,F(iv )又因n 2工n，再考虑C,D,E,F,因为Ca =Fa =C,Cb