P74 10. 已知正规文法G = ({S, B, C}, {a, b, c}, P, S)，其中P内包含如下产生式：
S::=aS | aB ??① B::=bB | bC ??②
C::=cC | c ??③ 请构造一个等价的有穷自动机。 解：M=({S, B, C, T}, {a, b, c}, M, {S}, {T})
M (S, a)=S M (S, a)=B M (S, b)=? M (S, c)=? M (B, a)=? M (B, b)=B M (B, b)=C M (B, c)=? M (C, a)=? M (C, b)=? M (C, c)=T M (C, c)=C
P74 11. 构造下列正规式相应的DFA： （1）1(0|1)*101
解：先构造该正规式的转换系统：
S 1(0|1)*101 Z S 1 1 (0|1)* 3 1 4 0 5 1 Z 0 S 1 1 ε 2 ε 1 3 1 4 ６ 0 5 1 Z 由上述转换系统可得状态转换集K={S, 1, 2, 3, 4, 5, Z}，状态子集转换矩阵如下表所示： I {S} {1, 2, 3} {2, 3} {2, 3, 4} {2, 3, 5} {2, 3, 4, Z} I0 Ф {2, 3} {2, 3} {2, 3, 5} {2, 3} {2, 3, 5} I1 {1, 2, 3} {2, 3, 4} {2, 3, 4} {2, 3, 4} {2, 3, 4, Z} {2, 3, 4} K 0 1 2 3 4 5 0 1 Ф 1 2 3 2 3 4 3 2 5 4 3 其对应的DFA状态转换图为：
现在对该DFA进行化简，最终得到下列化简后的状态转换图（先将其分成两组——终态组{5}和非终态组{0, 1, 2, 3, 4}，再根据是否可继续划分来确定最后的组数）： 0
0 1 1, 2 1 0 3 1 0 4 0 1 1 5 0 1 0 1 1 3 1 0 0 0 4 0 1 5 1 2 1 P74 12. 将图3.24非确定有穷自动机NFA确定化和最少化。
0 a 图3.24 NFA状态转换图
７
a
a, b 1 解：设(DFA)M = {K, VT, M, S, Z}，其中，K={[0], [0, 1], [1]}，VT ={a, b}，M： M ([1], a) =[0] M ([1], b) =Ф M ([0, 1], a) =[0, 1] M ([0, 1], b) =[1] M ([0], a) =[0, 1] M ([0], b) =[1] S=[1]，Z={[0], [0, 1]}
令[0, 1]=2，则其相应的状态转换图为： 现在对该DFA进行化简，先把状态分为两组： 终态组 {0, 2} 和非终态组 {1}，易于发现 {0, 2} 不可以继续划分，因此化简后的状态转换图如下：
a 0, 2 a b 1
a 0 a a 2 b b 1
P74 18. 根据下面正规文法构造等价的正规表达式：
S::=cC | a ??① A::=cA | aB ??② B::=aB | c ??③
C::=aS | aA | bB | cC | a ??④ 解：由③式可得 B= aB + c → B=a*c 由②式可得 A= cA + aB → A= c*aa*c 由①式可得 S= cC + a
由④式可得 C= aS + aA + bB + cC + a → C= c*( aS + aA + bB + a) →
C= c*( aS + ac*aa*c + ba*c + a) → S= cc*( aS + ac*aa*c + ba*c + a) + a = cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a) = (cc*a)*( cc*( ac*aa*c | ba*c | a) | a)
P142 1. 试分别消除下列文法的直接左递归（采用两种方法——重复法和改写法） （1）G[E]:
８
E::=T | EAT ??① T::=F | TMF ??② F::=(E) | i ??③ A::=+ | - ??④
M::=* | / ??⑤
解：先采用“重复法”： 再采用“改写法”：
E::=T{AT} E::=TE’ T::=F{MF} E’::= ATE’ | ε F::=(E) | i T::=FT’ A::=+ | - T’::=MFT’ | ε M::=* | / F::=(E) | i
A::=+ | -
M::=* | / （4）G[Z]:
Z::=V1 ??① V1::=V2 | V1iV2 ??② V2::=V3 | V2+V3 ??③ V3::=)V1* | ( ??④
解：先采用“重复法”： 再采用“改写法”：
Z::=V1 Z::=V1 V1::=V2 {iV2} V1::=V2 V1’ V2::=V3 {+V3} V1’::=i V2 V1’ | ε V3::=)V1* | ( V2::=V3 V2’
V2’::=+V3 V2’ | ε
V3::=)V1* | (
P142 2. 试分别消除下列文法的间接左递归 （2）G[Z]:
Z::=AZ | b ??①
９
A::=Z A | a ??②
解(一)：将②式代入①式可得，Z::=ZAZ | aZ | b 消除左递归后得到： Z::=(aZ | b)Z’ Z’::=AZZ’ | ε A::=ZA | a
解(二)：将①式代入②式可得，A::= AZA | bA | a 消除左递归后得到： Z::= AZ | b A::=bAA’ | aA’ A’::=ZAA’ |ε
P143 5. 对下面的文法G[E]:
E::=TE’ E’::=+E |ε T::=FT’
T’::=T |ε
F::=PF’
F’::=*F’ |ε
P∷＝(E) |a |b |∧
（1）计算这个文法的每个非终结符号的FIRST和FOLLOW； （2）证明这个文法是LL（1）文法；
（3）构造它的LL（1）分析表并分析符号串a*b+b; 解:（1）构造FIRST集：
FIRST(E’)={+, ε} FIRST(F’)={*, ε}
FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧} FIRST(T’)={ (，a，b, ε，∧}
构造FOLLOW 集：
规则一
１０