全部的短语：
第一个a (a1)是句子bbaacb相对于非终结符A (A1) (产生式A?a）的短语（直接短语）；
b1a1是句子bbaacb相对于非终结符A2的短语；
b2b1a1是句子bbaacb相对于非终结符A3的短语；
c是句子bbaacb相对于非终结符S1（产生式S?c）的短语（直接短语）；
a2cb3是句子bbaacb相对于非终结符B的短语；
b2b1a1a2cb3是句子bbaacb相对于非终结符S2的短语；
注：符号的下标是为了描述方便加上去的。
（2）句子（（（b）a（a））（b））的最右推导：
ST（AS）T（A（b））T（（SaA）（b））T（（Sa（a））（b）） T（（（b）a（a））（b））
相应的语法树是：
（3）解：iii*i+↑对应的语法树略。
最右推导：E TT=>F=>FP↑T FE↑T FET+↑T FEF+↑T FEP+↑T FEi+↑
TFTi+↑T FTF*i+↑TFTP*i+↑T FTi*i+↑TFFi*i+↑T FPi*i+↑
TFii*i+↑T Pii*i+↑Tiii*i+↑
12.证明：
充分性：当前文法下的每一符号串仅有一个句柄和一个句柄产生式T对当前符号串有唯一的最左归约T对每一步推导都有唯一的最右推导T有唯一的语法树。
必要性：有唯一的语法树T对每一步推导都有唯一的最右推导T对当前符号串有唯一的最左归约T当前文法下的每一符号串仅有一个句柄和一个句柄产生式
13.化简下列各个文法
（1）解：S→bCACdA→cSA| cCCC→cS | c
（2）解：S→aAB | fA | gA→e | dDAD→eAB→f
（3）解：S→ac
14.消除下列文法中的ε产生式
（1）解：S→aAS | aS | bA→cS
（2）解：S→aAA | aA | aA→bAc| bc | dAe| de
15.消除下列文法中的无用产生式和单产生式
（1）消除后的产生式如下：
S→aB | BC
B→DB | b
C→b
D→b | DB
（2）消除后的产生式如下：
S→SA | SB |（）|（S）|[] |[S]
A→() |（S）|[]|[S]
Bà[] |[S]
（3）消除后的产生式如下：
E→E+T | T*F | (E) | P↑F | i
T→T*F | (E) | P↑F | i
F→P↑F | (E) | i
P→(E) | i 第三章 习题解答
1．从略 2．
3 假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河
用到的状态1：狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸 4:狐狸和山羊在右岸5:狐狸和白菜在右岸 6:山羊和白菜在右岸F:全在右岸
4 证明：只须证明文法G:A→αB 或A→α （A,B∈VN, α∈VT+）
等价于G1:A→aB 或A→a (a∈VT+)
G1的产生式中 A→aB, 则B也有B→bC ,C→cD ?. 所以有 A →abc?B’,a,b,c?∈VT,B’∈VN
所以与G等价。
2）G的产生式A→αB，α∈VT+，因为α是字符串，所以肯定存在着一个终结符a， 使A→aB
可见两者等价，所以由此文法产生的语言是正规语言。 5
6 根据文法知其产生的语言是
L={ambnci| m,n,i≧1}
可以构造如下的文法VN={S,A,B,C}, VT={a,b,c}
P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c}
其状态转换图如下:
7 (1) 其对应的右线性文法是:
A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B
(2) 最短输入串011
(3) 任意接受的四个串
011,0110,0011,000011
(4) 任意以1打头的串.
8 从略。 9
（2）相应的3型文法
(i) S →aAS→bS A→aA A→bB B→a|aB B→b|bB
(ii) S→aA|a S→bB B→aB | bB A→aB A→b|bA
(iii) S→aA S→bB A→bA A→aC B→aB B→bC C→a|aC C→b|bC
(iv) S→bS S→aA A→aC A→bB B→aB B→bC C→a|aC C→b|bC
（3）用自然语言描述输入串的特征
(i) 以任意个(包括0)b开头，中间有任意个（大于1）a，跟一个b,还可以有一个由a,b组成的任意字符串
(ii) 以a打头，后跟任意个（包括0）b
(iii)以a打头，中间有任意个（包括0）b,再跟a,最后由一个a,b所组成的任意串结尾或者
以b打头，中间有任意个（包括0）a,再跟b,最后由一个a,b所组成的任意串结尾
(iv)以任意个（包括0）b开头,中间跟aa最后由一个a,b所组成的任意串结尾或者
以任意个（包括0）b开头，中间跟ab后再接任意（包括0）a再接b，最后由一个a,b所组成的任意串结尾
10 （1）G1的状态转换图：
G2的状态转换图：
(2) G1等价的左线性文法：
S→Bb,S→Dd,D→C,B→Db,C→Bc,B→Ab,B→ε,A→a
G2等价的右线性文法：
S→dD,S→aB,D→C,B→abC,B→bB,B→bA,B→ε,C→cA,A→a
（3）对G1文法,abb的推导序列是：
S=>aA=>abB=>abb
对G1’文法，abb的推导序列是：
S=>Bb=>Abb=>abb
对G2文法，aabca的推导序列是：
S=>Aa=>Cca=>Babca=>aabca
对G2’文法，aabca的推导序列是：
S=>aB=>aabC=>aabcA=>aabca
（4）对串acbd来说，G1,G1’文法都不能产生。
11将右线性文法化为左线性文法的算法：
（1）对于G中每一个形如A→aB的产生式且A是开始符，将其变为B→a,否则若A不是开始符，B→Aa;