第二章 习题解答
2.1
①该文法定义的是0到9这10个数字{0，1，2，3，4，5，6，7，8，9};
②同①;
③该文法定义的是{bna2∣n≥0};
2.2
①因为语言的句子要求由3的整数倍的a组成，所以在构造产生式时，要保证每次产生的a的个数是3。得到文法
G[S]：S→aaa|Saaa
②因为符号串中a、b的个数没有直接关系，所以，将句子分成两部分：an和b2m–1，分别进行构造，然后再合并。可由产生式
A→a|aA
得到an。而由产生式
B→b|bbB
1 / 9
得到b2m–1。由于n≥1，m≥1，所以得到文法
G[S]：S→AB
A→a|aA
B→b|bbB
③因为句子中，a和b的个数一样多，且a全部在句子的前半部分，b全部在句子的后半部分，所以在构造产生式时，可让a和b对称出现。得文法
G[S]：S→aSb|ab
④因为句子中a、b、c的个数没有直接关系，所以分别构造生成an、bm、ck的产生式，然后再合成。可由产生式
A→aA|
得到an。而由产生式
B→bB|
得到bm。再由产生式
C→cC|
2 / 9
得到ck。所以得到文法
G[S]： S→ABC
A→aA|
B→bB|
C→cC|
⑤文法为
G[S]：S→(+|–)(ABC|2|4|6|8)|0
C→0|2|4|6|8
B→BA|B0|
A→1|2|3|…|9
⑥能被5整除的整数的末位数必定是0或5。所以只要保证生成的整数末位数字是0或5即可。据此，构造描述能被5整除的整数集合的文法如下：
G[S]：S→(+|-)A(0|5)
A→0|1|2|3|4|5|6|7|8|9|AA
3 / 9
如果还要求整数除0外，均不以0开头，则文法为
G[S]：S→(+|-)(A(0|5)|0|5)
A→AB|C
B→0|C|BB
C→1|2|3|4|5|6|7|8|9
⑦由于文法的句子{a, b}+，因此文法的句子可分解为两种情形：
以a打头的符号串；
以b打头的符号串。
于是只要在构造产生式时保证每次产生相同个数的a和b即可。可以构造文法如下。
G[S]：S→aSbS|bSaS|ab|ba
或
G[S]：S→aSb|bSa|abS|Sab|baS|Sba|ab|ba
2.3略
4 / 9
2.4 0型文法
2.5 P={S→aD∣eE，D→bF，F→cA，E→dB，A→bC，C→eB，B→d}
2.6
①3274的最左推导为:
NNDNDDNDDDDDDD3DDD32DD
327D3274
3274的最右推导为:
NNDN4ND4N74ND74N274
D2743274
②65173的最左推导为:
NNDNDDNDDDNDDDDDDDDD6DDDD
65DDD651DD6517D65173
65173的最右推导为:
5 / 9
NNDN3ND3N73ND73N173
ND173N5173D517365173
2.7
句型 +*TP*i(+ET)的短语有
*TP、i、+ET、(+ET)、*i(+ET)、+*TP*i(+ET)
句型 +*TP*i(+ET)的简单短语有
*TP、i、+ET
句型 +*TP*i(+ET)的句柄为
*TP
2.8
①要判别文法是否具有二义性，只要判别文法是否定义有这样的句子：该句子对应着两棵(包括两棵)以上语法树，或者说有两个(包括两个)以上不同的最右(左)推导；或者说在对该句子进行规范归约过程中，其规范句型的句柄不唯一。
本题文法是二义性的。因为对于句子abc，存在两个不同的最左推导序列：
6 / 9
SABabBabc 和 SABaBabc
②文法是二义性的。因为对于句子123，存在两个不同的最左推导序列：
1212134124123
和 123421421227 / 9
123
2.9
①产生式E→E和F→F、G→G是有害产生式，应删去。F，P，G三个非终结符号无法推导出终结符号串，因此，它们对应的产生式为无用产生式，应删去。非终结符号Q无法从识别符号推导出来，因此，Q所对应的产生式也为无用产生式，也应删去。由于删去了F所对应的产生式后，S也无法从识别符号推导出来，故也应删去。压缩后的文法为
G[Z]： Z→E+T
E→T
T→T*i|i
②使其不含有形如A→B(A、B均为非终结符号)的产生式。
将M代入F，然后将改写后的F代入T，最后将改写后的T代入S，于是将文法改为
G[S]：S→aFbT|Tcb|Fa|Tb|abF|c|abc|cMb
F→Tb|abF|c|abc
T→Fa|Tb|abF|c|abc|cMb
M→abF|c
8 / 9
文法中不再有形如A→B(A、B均为非终结符号)的产生式。
友情提示：部分文档来自网络整理，供您参考！文档可复制、编制，期待您的好评与关注！
9 / 9
