1、蒋立源编译基本知识第三版第三章知识题与答案解析修改后第3章 习题3-1 试构造一右线性文法，使得它与如下的文法等价SAB AUT UaU|a DbT|b BcB|c 并根据所得的右线性文法，构造出相应的状态转换图。3-2 对于如题图3-2所示的状态转换图(1) 写出相应的右线性文法；(2) 指出它接受的最短输入串；(3) 任意列出它接受的另外4个输入串；(4) 任意列出它拒绝接受的4个输入串。3-3 对于如下的状态转换矩阵：(1) 分别画出相应的状态转换图；(2) 写出相应的3型文法；(3) 用自然语言描述它们所识别的输入串的特征。3-4 将如下的NFA确定化和最小化：3-5 将如题图3-5所
2、示的具有动作的NFA确定化。题图3-5 具有动作的NFA 3-6 设有文法GS：SaA AaA|bB BbB|cC|c CcC|c试用正规式描述它所产生的语言。 3-7 分别构造与如下正规式相应的NFA。(1) (0* |1)(1* 0)*(2) b|a(aa*b)*b 3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应的DFA。第3章 习题答案3-1 解：根据文法知其产生的语言是:LG=ambnci| m,n,i1可以构造与原文法等价的右线性文法:SaA AaA|bB BbB|cC|c CcC|c其状态转换图如下:3-2 解:(1) 其对应的右线性文法是GA:A 0D B0A|1
3、C C0A|1F|1D0B|1C E0B|1C F1A|0E|0(2) 最短输入串为011(3) 任意接受的四个输入串为：0110,0011,000011,00110(4) 任意拒绝接受的输入串为： 0111，1011，1100，10013-3 解:(1) 相应的状态转换图为：(2) 相应的3型文法为：() SaA|bS AaA|bB|b BaB|bB|a|b() SaA|bB|a AbA|aC|a|b BaB|bC|b CaC|bC|a|b() SaA|bB|b AaB|bA|a BaB|bB|a|b () SbS|aA AaC|bB|a BaB|bC|b CaC|bC|a|b(3) 用自然
4、语言描述的输入串的特征为：() 以任意个(包括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，再接
5、b，最后由一个a,b所组成的任意串结尾。3-4 解：(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)所示。现将DFA M最小化：()初始分划由两个子集组成，即0:1,2, 3,4()为得到下一分划，考察子集1,2。因为2b =3 3,4但 1b = 故1和2可区分，于是便得到下一分划1: 1, 2, 3,4()又因10 ，
6、再考虑3,4，因为3b =3 3,4而 4b = 故3和4可区分，从而又得到2: 1, 2, 3, 4此时子集已全部分裂，故最小化的过程宣告结束，M即为状态数最小的DFA。(2) 将NFA M确定化后得DFA M，其状态转换矩阵如答案图3-4-(2)之(a)所示，给各状态重新命名，即令： S=1, A=2, B,C=3且由于3的组成中含有M的终态C，故3为DFA M的终态。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-4-(2)之(b)及(c)所示。现将DFA M最小化：()初始分划由两个子集组成，即0:1,2, 3()为得到下一分划，考察子集1,2。因为2b =2 1,2但
7、1b = 故1和2可区分，于是便得到下一分划1: 1, 2, 3此时子集已全部分裂，故最小化的过程宣告结束，M即为状态数最小的DFA。(3) 将NFA M确定化后得DFA M，其状态转换矩阵如答案图3-4-(3)之(a)所示，给各状态重新命名，即令： S=1, A=2, S,B=3且由于3的组成中含有M的终态B，故3为DFA M的终态。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-4-(3)之(b)及(c)所示。现将DFA M最小化：()初始分划由两个子集组成，即0:1,2, 3()为得到下一分划，考察子集1,2。因为2b =3但 1b = 故1和2可区分，于是便得到下一分划1
8、: 1, 2, 3此时子集已全部分裂，故最小化的过程宣告结束，M即为状态数最小的DFA。(4) 将NFA M确定化后得DFA M，其状态转换矩阵如答案图3-4-(4)之(a)所示，给各状态重新命名，即令： A=1, B,C=2, B=3, C=4且由于2和4的组成中含有M的终态C，故2和4组成了DFA M的终态集Z。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-4-(4)之(b)及(c)所示。 现将DFA M最小化：()初始分划由两个子集组成，即0:1,3, 2,4()为得到下一分划，考察子集1,3。因为1a =2 2,4但 3a =1 1,3故1和3可区分，于是便得到下一分划
9、1: 1, 3, 2,4()又因10，再考虑2,4，因为2a =4a =1, 2b =4b =4所以2和4不可区分，故子集S,B已不能再分裂。此时2 =1 ，子集分裂的过程宣告结束。() 现选择状态2作为2,4的代表，将状态4从状态转换图中删去，并将原来引至4的矢线都引至2，这样，我们就得到了最小化后的DFA M如答案图3-4-(4)之(d)所示。3-5 解：(1) 将具有动作的NFA M确定化后得DFA M，其状态转换矩阵如答案图3-5-(1)之(a)所示，给各状态重新命名，即令： S,B,C=1, A=2, B,C =3, C=4且由于1,3和4的组成中均含有M的终态C，故1,3和4组成了
10、DFA M的终态集Z。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-5-(1)之(b)及(c)所示。(2) 将具有动作的NFA M确定化后得DFA M，其状态转换矩阵如答案图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组成了DFA M的终态集Z。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-5-(2)之(b)及(c)所示。3-6 解：首先将文法写成方程组：S=aA (1)A=aA+b
11、B (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)所示：(2) 构造与正规式 b|a(aa*b)*b 相应的NFA的步骤如答案图3-7-(2)所示：答案
12、图3-7-(2) 正规式 b|a(aa*b)*b 的NFA3-8 解：首先，构造与正规式(a|b)*(aa|bb)(a|b)*相应的NFA M，其构造步骤如答案图3-8(a)所示：其次，将答案图3-8(a)所示的具有动作的NFA M确定化后得到DFA M，其状态转换矩阵如答案图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的组成中均含有NFA M的终态Z，故C,D,E和F组成了DFA M的终态集Z。于是，将NFA
13、M确定化后所得DFA M的状态转换矩阵和状态转换图如答案图3-8(c)及(d)所示。(e) 对DFA M最小化后所得的DFA M的状态转换图答案图3-8 最后，将所得DFA M最小化：()初始分划由两个子集组成，即0:S,A,B, C,D,E,F()为得到下一分划，考察子集S,A,B。因为S,Ba =A S,A,B但 Aa =C C,D,E,F故S,B和A可区分，于是便得到下一分划1: S,B, A, C,D,E,F()因1 0 ，考虑S,B，因为Sb =B S,B但 Bb =D C,D,E,F故S和B可区分，于是便得到下一分划2: S, B, A, C,D,E,F() 又因2 1 ，再考虑C,D,E,F，因为Ca =Fa =C, Cb =Fb =E所以C和F等价；同理可得D和E等价。又因为Ca =C, Da =F, Cb =E, Db =D而C和F等价，D和E等价，所以C和D也等价，故C,D,E,F这4个状态等价。此时3 =2 ，子集分裂的过程宣告结束。()现选择状态C作为C,D,E,F的代表，将状态D,E,F从状态转换图中删去，并将原来引至D,E,F的矢线都引至C，这样，我们就得到了最小化后的DFA M如答案图3-8(e)所示,此DFA M即为所求的与正规式(a|b)*(aa|bb)(a|b)*相应的DFA。
