第三章1、L(G[S])={ abc }2、L(G[N])={ n位整数或空字符串| n>0 }3、G[E]：E—>E+D | E-D | DD—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、L(G[Z])={ a n b n | n>0 }5、(1) 考虑不包括“0”的情况G[S]：S—>0S | ABC | 2 | 4| 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8考虑包括“0”的情况：G[S]：S—>AB | CB—>AB | CA—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>0 | 2 | 4 | 6 | 8(2)方法1：G[S]：S—> ABC | 2 | 4 | 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8方法2：G[S]：S—>AB | CB—> AB | 0B | C | 0A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>2 | 4 | 6 | 86、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I7、<表达式><表达式>*<表达式><表达式>+<表达式>i i i<表达式><表达式>+<表达式>i <表达式>*<表达式>i i8、是有二义性的，因为句子abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S => Ac => abc 最左推导2：S => aB => abc 9、(1)(2) 该文法描述了变量a 和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导： 最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()() 最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S => ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因为从文法的开始符E 出发可推导出E+T*F ，推导过程如下：E => E+T => E+T*F ，所以E+T*F 是句型。

从子树和短语之间的关系可知：E+T*F 是句型E+T*F 相对于E 的短语；T*F 是句型E+T*F 相对于T 的短语，也是简单短语和句柄。

13、(1) 最左推导：S => ABS => aBS => aSBBS => aBBS => abBS => abbS => abbAa => abbaa(2) S —>ABS | Aa |ε A —>aB —>SBB | b(3) 首先为了区别句子abbaa 中的a 和b ，把它写成a 1b 1b 2a 2a 3 该句子的短语有：a 1b 1b 2a 2a 3，b 1b 2，a 2a 3，a 1，a 2，b 1，b 2，ε 直接短语有：a 1，a 2，b 1，b 2，ε 句柄：a 114、(1) G[S]：S —>ABA —>aAb |εB —>aBb |εS S S *+ S S a aa(2) G[S]：S —>1S0 | A A —>0A1 |ε (3) G[S]：S —>0S0 | aSa | a16、(1) G[A]：A —>aA |ε(2)G[A]：A —> aA | aB B —> bB | b (3)G[A]：A —>aA | B B —> bB | C C —>cC |ε17、习题6、习题7和习题7中的文法所描述的语言都是由变量i 、+、-、*、/、（和）组成算术表达式，因此它们之间是等价的。

第四章参考答案 第1题：确定化： S A B C Z重新命名，令{AB}为B 、{AC}为C 、{ABZ}为Z 其中S(3)确定化：0 1 2 3 4重新命名，以0、1、2、3、4代替{S},{A}, {AB},{AZ},{ABZ}得DFA 其中0为初态，3，4为终态第2题： A B C D E F重新命名，以A 、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ代替{X},{Z },{XZ },{ Y },{ XY },{XYZ}得DFA 其中Aa,b第3题： 确定化：A B C D E F G重新命名，以A 、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ代替{S},{VQ },{QU },{ VZ },{ V },{QUZ},{Z}得DFA 其中A第4题： (1)A B C重新命名，以Ａ、Ｂ、Ｃ代替{0}、{01}、{1}得ＤＦＡ 其中A 为初态，A ，B 为终态最小化：初始分划得终态组{A,B}，非终态组{C} Π0：{A,B}，{C}对终态组进行审查，判断A 和B 是等价的，故这是最后的划分 重新命名，以A 、C 代替{A,B}、{C}得DFAa b –+A A C CA(2)这是DFA ，直接最小化初始分划得：终态组{0}，非终态组{1,2,3,4,5} Π0：{0}，{1,2,3,4,5}对{1,2,3,4,5}进行审查：∵{4} 输入a 后到达{0}，{1,2,3,5}输入a 后到达{1,3,5}，故得到新分划 {0,1,3,5}，{4} Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查：∵{1,5} 输入b 后到达{4}，{2,3} 输入b 后到达{2,3}，故得到新分划 {1, 5}，{2,3} Π2：{0}，{4}，{1, 5}，{2,3}对{1, 5}，{2,3}进行审查： {1, 5} 输入a 后到达{1, 5}{2} 输入a 后到达{1}，{3} 输入a 后到达{3}，故得到新分划{2}，{3} Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分划了重新命名，以0，2，3，4，1代替{0}，{2}，{3}，{4}，{1, 5}得DFA 略 第7题首先判断E ，F 为多余状态 根据正则文法转化为NFA 的方法构造NFA确定化：bbbb ba baa S A aQ b Za B D0 1 2 3 4 5 6最小化：初始分划得：终态组｛3,4｝，非终态组｛0,1,2,5,6｝ Π0：｛3,4｝,｛0,1,2,5,6｝对｛0,1,2,5,6｝进行审查： {1,2}输入b 到达｛3,4｝，而{0,5,6}输入b 到达｛2,5,6｝，故得到新分划｛1,2｝,｛0,5,6｝ Π1：｛3,4｝,｛1,2｝,｛0,5,6｝ 对｛0,5,6｝进行审查：{0}经过b 到达｛２｝，{5,6}经过b 到达｛5,6｝，故得到新分划｛0｝｛5,6｝ Π3：{0}，{1,2}，{3,4}，{5,6} 这是最后划分了。

重新命名，以0，1，3，5代替{0}，{1,2}，{3,4}，{5,6}得DFA 略第9题这是DFA ，直接最小化 初始分划得：终态组｛6,7｝，非终态组｛1,2,3,4,5｝ Π0：｛6,7｝,｛1,2,3,4,5｝对｛1,2,3,4,5｝进行审查： {1,2}输入b 到达｛2｝，而{3,4}输入b 到达｛6,7｝，{5}输入b 不会有任何动作，故得到新分划｛1,2｝,｛3,4｝,{5} Π1：｛6,7｝,｛3,4｝,｛5｝,｛1,2｝这是最后划分了。

重新命名，以1，3，5，6代替｛1,2｝,｛3,4｝,｛5｝,｛6,7｝得DFA所识别的语言是b*a (c| da)*bb*--第11题根据正则文法（左线性文法）转化为NFA 的方法构造NFA ：确定化： 0 1 2重新命名，以0、1、2代替{ZS}、{A}、{AS}得DFA所识别的语言是：ε| (a|b) a (ba|a)*第13题（1） 假设d {A,B,…,Y,Z} n {0,1,2,…,8,9}，文法可以等价得化为：<单词>—> <标识符> | <整数><标识符>—> <标识符>d | <标识符>n | d <整数>—><整数>n | n（2） 根据正则文法（左线性文法）转化为NFA 的方法构造NFA ：重新命名状态，令A 、B 、C 分别代表<单词>、<标识符>、<整数>-- a第五章 习题参考答案1、(1) 对(a,(a,a)的最左推导为：S (T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))对(((a,a),∧,(a)),a) 的最左推导为：S (T)(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T),S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),∧,S),S)(((a,a),∧,(T)),S)(((a,a),∧,(S)),S)(((a,a),∧,(a)),S)(((a,a),∧,(a)),a)对((( a, a ), ∧, ( a )), a )的最左推导为：S ⇒ ( T ) ⇒ ( T, S ) ⇒ ( S, S ) ⇒ (( T ), S ) ⇒ (( T, S ), S )⇒(( T, S, S ), S )⇒ (( S, S, S ), S ) ⇒ ((( T ), S, S ), S ) ⇒ ((( T, S ), S, S ), S ) ⇒ ((( S, S ), S, S ), S ) ⇒ ((( a, S ), S, S ), S ) ⇒ ((( a, a ), S, S ), S ) ⇒ ((( a, a ), ∧, S ), S ) ⇒ ((( a, a ), ∧, ( T )), S ) ⇒ ((( a, a ), ∧, ( S )), S ) ⇒ ((( a, a ), ∧, ( a )), S ) ⇒ ((( a, a ), ∧, ( a )), a )对((( a, a ), ∧, ( a )), a )的最左推导为：S ⇒ ( T ) ⇒ ( T, S ) ⇒ ( T, a ) ⇒ ( S, a ) ⇒ (( T ), a ) ⇒ (( T, S ), a )⇒ (( T, ( T )), a ) ⇒ (( T, ( S )), a ) ⇒ (( T, ( a )), a ) ⇒ (( T, S, ( a )), a ) ⇒ (( T, ∧, ( a )), a ) ⇒ (( S, ∧, ( a )), a ) ⇒ ((( T ), ∧, ( a )), a ) ⇒ ((( T, S ), ∧, ( a )), a ) ⇒ ((( T, a ), ∧, ( a )), a ) ⇒ ((( S, a ), ∧, ( a )), a ) ⇒ ((( a, a ), ∧, ( a )), a )(2) 改写文法为：0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→εS: T:NNY入口a^ ( ) Y YRead(w)TRead(w)NN出口出错入口SN 出口 入口Y，NSN出口Read(w)(3)非终结符FIRST集FOLLOW集S {a,∧,(} {#,,,)}T {a,∧,(} {)}....N {,,ε}.{)}....对左部为N的产生式可知：SELECT(S→a)∩SELECT(S→∧) ∩SELECT(S→( T ))=SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}=所以文法是LL(1)的。