《蒋立源编译原理-第三版-第三章-习题与答案(修改后).doc》由会员分享，可在线阅读，更多相关《蒋立源编译原理-第三版-第三章-习题与答案(修改后).doc（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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所示得具有动作得NFA确定化。题图3-5 具有动作得N
2、FA 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 F
3、1A|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个
4、)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 解
5、:(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
6、与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,
7、 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此时子集已全部分裂,故最小化得过程
8、宣告结束,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,
9、因为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得状
10、态转换矩阵与状态转换图如答案图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
11、 (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
12、 得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得状态转换矩阵与状态转
13、换图如答案图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。