编译原理-第三版-第三章-习题与答案（修改后）.doc

第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所示得具有动作得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)*b3-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|1C      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) 用自然语言描述得输入串得特征为:() 以任意个(包括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  解:(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 =33,4但          1b =故1与2可区分,于就是便得到下一分划1: 1, 2, 3,4()又因10 ,再考虑3,4,因为3b =33,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 =21,2但          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: 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 =22,4但          3a =11,3故1与3可区分,于就是便得到下一分划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组成了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+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)所示:(2) 构造与正规式 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)所示:其次,将答案图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 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 =AS,A,B但          Aa =CC,D,E,F故S,B与A可区分,于就是便得到下一分划1: S,B, A, C,D,E,F()因1 0 ,考虑S,B,因为Sb =BS,B但          Bb =DC,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。