《编译原理》习题解答
S∷＝aAb
A∷＝BcA | B
B∷＝idt |ε
（1）SaAbaBcAbaidtcAbaidtcBcAb 句型但不是句子；
（3）SaAbaBbaεbab 是句型也是句子；
（5）SaAbaBcAbaidtcAbaidtcBcAbaidtcidtcBbaidtcidtcidtb句型也是句子。
P39 10、给定文法：
S∷＝aB | bA
A∷＝aS | bAA | a
B∷＝bS | aBB|b 该文法所描述的语言是什么？
L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。
P39 11、试分别描述下列文法所产生的语言（文法开始符号为S）：
（1） S∷＝0S | 01
（2） S∷＝aaS | bc
（3） S:: =aSd | aAd
A:: =aAc | bc
（4） S:: =AB
A:: =aAb | ab
B:: =cBd | ε
（1） L(G)＝{0n1| n≥1}；
（2） L(G)＝{a2nbc | n≥0}；
（3） L(G)＝{aibcjdk | i, j, k≥1, i=j+k-1}；或者 L(G)＝{aj+k-1bcjdk | j, k≥1}；
（4） L(G)＝{anbncmdm | m≥0, n≥1}。
P39 15. 设文法G规则为：
S：：=AB
B：：=a|Sb
A：：=Aa|bB
对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。
（2）baabaab
（2） S
A B
A a S b
b B A B
a b B a
a
句型baabaab的短语a, ba, baa, baab, baabaab，简单短语a，句柄 a
P40 19. 证明下述文法是二义的
1) S::=iSeS|iS|i
3) S::=A|B
A::=aCbA|a
B::=BCC|a
C::=ba (最简单的就是a为句型)
1) 对于句子iiieii可构造两棵不同的语法树，所以证明该文法是二义的。
P41 24. 下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？
1.S::=aB B::= cB B::=b C::=c
2.S::=aB B::=bC C::=c C::=ε
3.S::=aAb aA::=aB aA::=aaA B::=b A::=a
4.S::=aCd aC::=B aC::=aaA B::=b
5.S::=AB A::=a B::=bC B::=b C::=c
6. S::=AB A::=a B::=bC C::=c C::=ε
7. S::=aA S::= ε A::=aA A::=aB A::=a B::=b
8. S::=aA S::= ε A::=bAb A::=a
正规文法 1 2 7
上下文无关文法 5 6 8
上下文有关文法 3
短语结构文法 4
P42 29. 用扩充的BNF表示以下文法规则：
1． Z::=AB|AC|A
2． A::=BC|BCD|AXZ|AXY
3． S::=aABb|ab
4． A::=Aab|ε
解:
1．Z::=A（B|C|ε）::=A[B|C]
2．A::=BC（ε|D）{X（Z|Y）}::= BC[D] {X（Z|Y）}
3．A::=a((AB|ε)b) ::= a[AB]b
4．A::={ab}
P74 4. 画出下列文法的状态图：
Z：：=Be
B：：=Af
A：：=e|Ae 并使用该状态图检查下列句子是否该文法的合法句子：f, eeff, eefe。
由状态图可知只有eefe是该文法的合法句子。
P74 5. 设右线性文法G=({S, A, B}, {a, b}, S, P)，其中P组成如下：
S：：=bA A：：=bB A：：=aA A：：=b B：：=a
画出该文法的状态转换图。
P74 8. 设 (NFA) M = ( {A, B}, {a, b}, M, {A}, {B} )，其中M定义如下：
M (A, a) = {A, B} M (A, b) = {B} M (B, a) = ø M (B, b) = {A, B}
请构造相应确定有穷自动机(DFA) M’。
解：构造一个如下的自动机(DFA) M’， (DFA) M’={K’, {a, b}, M’, S’, Z’}
K’的元素是[A] [B] [A, B]
由于M（A, a）={A, B}，故有M’（[A], a）=[A, B]
同样 M’（[A]，b）=[B]
M’（[B]，a）= ø
M’（[B]，b）=[A，B]
由于M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U ø= {A，B}
故 M’（[A，B]，a）= [A，B]
由于M（{A，B}，b）= M（A，b）U M（B，b）={B}U {A，B} = {A，B}
故 M’（[A，B]，b）= [A，B]
S’=[A]，终态集Z’={[A，B]，[B]}
重新定义：令0=[A] 1=[B] 2=[A, B]，则DFA如下所示：
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
解：先构造该正规式的转换系统：
由上述转换系统可得状态转换集K={S, 1, 2, 3, 4, 5, Z}，状态子集转换矩阵如下表所示：
I | I0 | I1 | K | 0 1 |
{S} | Ф | {1, 2, 3} | 0 | Ф 1 |
{1, 2, 3} | {2, 3} | {2, 3, 4} | 1 | 2 3 |
{2, 3} | {2, 3} | {2, 3, 4} | 2 | 2 3 |
{2, 3, 4} | {2, 3, 5} | {2, 3, 4} | 3 | 4 3 |
{2, 3, 5} | {2, 3} | {2, 3, 4, Z} | 4 | 2 5 |
{2, 3, 4, Z} | {2, 3, 5} | {2, 3, 4} | 5 | 4 3 |
其对应的DFA状态转换图为：
现在对该DFA进行化简，最终得到下列化简后的状态转换图（先将其分成两组——终态组{5}和非终态组{0, 1, 2, 3, 4}，再根据是否可继续划分来确定最后的组数）：
P74 12. 将图3.24非确定有穷自动机南京有什么大学NFA确定化和最少化。
解：设(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}
不可以继续划分，因此化简后的状态转换图如下：
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 | b
a*c | a) | a)
P142 1. 试分别消除下列文法的直接左递归（采用两种方法——重复法和改写法）
（1）G[E]:
E::=T | EAT ……①
T::=F | TMF ……②
F::=(E) | i ……③
A::=+ | - ……④
M::=* | / ……⑤
发布评论