第 2 章 习题解答1.文法 GS为： S-Ac|aB A-ab B-bc 写出 L(GS)的全部元素。 答案 S=Ac=abc 或 S=aB=abc 所以 L(GS)=abc =2. 文法 GN为： N-D|ND D-0|1|2|3|4|5|6|7|8|9 GN的语言是什么？ 答案 GN的语言是 V+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD. =NDDDD.D=D.D =3.已知文法 GS： SdAB AaA|a B|bB 问：相应的正规式是什么？GS能否改写成为等价的正规文法？ 答案 正规式是 daa*b*； 相应的正规文法为(由自动机化简来)： GS:SdA Aa|aB BaB|a|b|bC CbC|b 也可为(观察得来):GS:SdA Aa|aA|aB BbB| =4.已知文法 GZ： Z-aZb|ab 写出 L(GZ)的全部元素。 答案 Z=aZb=aaZbb=aaa.Z.bbb= aaa.ab.bbb L(GZ)=anbn|n=1 =5.给出语言a nbncm|n=1,m=0的上下文无关文法。 分析 本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A-,AVn，（VnVt） *，注意关键问题是保证 anbn的成立，即“a 与 b 的个数要相等”，为此，可以用一条形如 A-aAb|ab 的产生式即可解决。 答案 构造上下文无关文法如下： S-AB|A A-aAb|ab B-Bc|c 扩展 凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路是这样的： 要求符合 anbncm，因为 a 与 b 要求个数相等，所以把它们应看作一个整体单元进行，而 cm做为另一个单位，初步产生式就应写为 S-AB，其中 A 推出anbn，B 推出 cm。因为 m 可为 0，故上式进一步改写为 S-AB|A。接下来考虑 A,凡是要求两个终结符个数相等的问题，都应写为 A-aAb|ab 形式，对于 B 就很容易写成 B-Bc|c 了。 =6 .写一文法，使其语言是偶正整数集合。 要求： (1)允许 0 开头； (2)不允许 0 开头。 答案 (1)允许 0 开头的偶正整数集合的文法 E-NT|G|SFM T-NT|G N-D|1|3|5|7|9 D-0|G G-2|4|6|8 S-NS| F-1|3|5|7|9|GM-M0|0 (2)不允许 0 开头的偶正整数集合的文法 E-NT|D T-FT|G N-D|1|3|5|7|9 D-2|4|6|8 F-N|0 G-D|0 =7.已知文法 G： E-E+T|E-T|T T-T*F|T/F|F F-(E)|i 试给出下述表达式的推导及语法树 (1)i; (2)i*i+i (3)i+i*i (4)i+(i+i) 答案 (1)E=T=F=i (2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i (3)E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i (4)E=E+T=T+T=F+T=i+T=i+F=i+(E)=i+(E+T)=i+(T+T)=i+(F+T) =i+(i+T)=i+(i+F)=i+(i+i)8 .为句子 i+i*i 构造两棵语法树，从而证明下述文法 G是二义的。 表达式-表达式运算符表达式|(表达式)|i 运算符-+|-|*|/ 答案 可为句子 i+i*i 构造两个不同的最右推导: 最右推导 1 表达式=表达式运算符表达式 =表达式运算符i =表达式* i =表达式运算符表达式* i =表达式运算符i * i =表达式+ i * i = i + i * i 最右推导 2 表达式=表达式运算符表达式 =表达式运算符表达式运算符表达式 =表达式运算符表达式运算符 i =表达式运算符表达式 * i = 表达式运算符i * i =表达式+ i * i = i + i * i 所以，该文法是二义的。=9. 文法 GS为： S-Ac|aB A-ab B-bc 该文法是否为二义的？为什么？ 答案 对于串 abc (1)S=Ac=abc (2)S=aB=abc 即存在两不同的最右推导 所以，该文法是二义的。 =10.考虑下面上下文无关文法： S-SS*|SS+|a (1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树。 (2) GS的语言是什么？ 答案 (1)此文法生成串 aa+a*的最右推导如下 S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a* (2)该文法生成的语言是即加法和乘法的逆波兰式, =11. 令文法 GE为: E-E+T|E-T T-T*F|T/F|F F-(E)|I 证明 E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=E+T=E+T*F，所以 E+T*F 句型 此句型相对于 E 的短语有:E+T*F；相对于 T 的短语有 T*F, 直接短语为：T*F；。句柄为：T*F 12.已知文法 GE: EET+|T TTF* | F FF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄. 答案 该句型对应的语法树如下：该句型相对于 E 的短语有 FF*；相对于 T 的短语有 FF*,F;相对于 F 的短语有 F;F;简单短语有 F;F;句柄为 F. 13.一个上下文无关文法生成句子 abbaa 的推导树如下： (1)给出串 abbaa 最左推导、最右推导。 (2)该文法的产生式集合 P 可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。(1)串 abbaa 最左推导: S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa 最右推导： S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa (2)产生式有：SABS |Aa| Aa BSBB|b (3)该句子的短语有 a1b1b2a2a3、a 1、b 1、b 2、b 1b2、a 2a3、a 2； 直接短语有 a1、b 1、b 2、a 2； 句柄是 a1。 =14.给出生成下列语言的上下文无关文法。 （1） a nbnambm |n，m=0 (2) 1 n0m 1m0n| n，m=0 （3）WaW r|W 属于0|a*，W r表示 W 的逆 答案 （1）a nbnambm| n，m=0 S-AA A-aAb| (2) 1n0m 1m0n| n，m=0 S-1S0|A A-0A1| （3）WaW r|W 属于0|a*，W r表示 W 的逆 S-0S0|1S1| =15 .给出生成下列语言的三型文法。 (1) an|n =0 (2) anbm|n,m=1 (3)anbmck|n,m,k=0 答案 (1) an|n =0 的三型文法为： S-aS| (2) anbm|n,m=1 的三型文法为： S-aA A-aA|bB B-bB| (3)anbmck|n,m,k=0 的三型文法为: A-aA|bB|cC| B-bB|cC| C-cC| =16.构造一文法产生任意长的 a,b 串，使得 |a|bb|b 第 1 个产生式为递归定义，由于在第 2 个产生式中 B 被定义为 1 或 2 个b，所以第 1 个产生式可以保证 b 的个数在|a|与 2|a|之间，而 a 与 b 的位置可以任意排布，所以此文法即为所求，注意第 1 个产生式中要包括 s。 =17.下面的文法产生 a 的个数和 b 的个数相等的非空 a,b 串 S-aB|bA B-bS|aBB|b A-aS|bAA|a 其中非终结符 B 推出 b 比 a 的个数多 1 个的串，A 则反之。 说明该文法是二义的。 对上述文法略作修改，使之非二义，并产生同样的语言。（略做修改的含义是：不增加非终结符。） 答案 句子 aabbab 有两种不同的推导。 S=aB=aaBB=aabB=aabbS=aabbaB=aabbab S=aB=aaBB=aabSB=aabbAB=aabbaB=aabbab 即它可以产生两棵不同的语法树，故它是二义的。 修改后的无二义文法如下： S-aBS|bAS|aB|bA B-aBB|b A-bAA|a =18.给出 0，1，2，3 型文法的定义。 答案 乔姆斯基(chomsky)把