.
第2章 习题
2-1 设有字母表A={a,b,c,…,z}，A={0,1,…,9}，试回答下列问题：
2 1
(1) 字母表A上长度为2的符号串有多少个？ (2) 集合AA含有多少个元素？ 中的全部长度
1
21*
不大于3的符号串。 ∪列出集合A(AA)(3)
211
2-2 试分别构造产生下列语言的文法：
nn
pmn
b|n≥0}；（1）{a |n,m,p≥0}；bc（2）{a #d|n≥0}；{a）#b|n≥0}∪{c（3 w的逆序排
nnnn
r*r
列4（）{w#w }# | w∈{0,1},w；是 ）任何不是以0打头的所有奇整数所组成的集合；（5 1所组成的符号串的集合。）所有由偶数个（60和偶数个
2-3 试描述由下列文法所产生的语言的特点： A→bA（1）S→10S0 S→aA A→a （2）S→SS A→εA→1A0 S→1A0
A→CA→1A S→B0 ）S→1A（3 C→1C0 C→εB→B0 B→C S→a（4）S→aSS 试证明文法2-4
aDb|ab →→cC|c DbBc|bc CAB|DC A→aA|a B→→ S 为二义性文法。 2-5 对于下列的文法aSb|c
→SAB|c A→→bA|a B的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全试给出句子bbaacb 部短语。.
.
化简下列各个文法2-6
c C→cS|→bAB|cSB (1) S→aABS|bCACd A→bAB|cSA|cCC BbE|f B→A→dDA|e (2) S→aAB|E
g E→fA| C→cAB|dSD|a D→eAbC|d SA C→(3) S→ac|bA A→cBC B→ 产生式2-7 消除下列文法中的ε- ε(1) S→aAS|b A→cS| (2) S→aAA A→bAc|dAe|ε
2-8 消除下列文法中的无用产生式和单产生式B D→C C→b B→DB|(1) S→aB|BC A→aA|c|aDb
[S]|[ ] B→A→B|(S)|( ) |SB|A (2) S→SA(E)|i |P P→→(3) E→E+T|T TT*F|F F→P↑F
习题答案第2章
答：2-1 (1) 26*26=676 (2) 26*10=260
共有(3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz, a00,a01,...,zzz}, 26+26*36+26*36*36=34658个
解：2-2 },S)
→ε| aSb对应文法为G(S)=(1)
},S) Y→cY|ε X→bX|Y,(2) 对应文法为G(S)= u2192aS|X,b,c,d,#}, {S→X, S→Y, 为文对(3)应法G(SX→aXb|#, Y→cYd|# },S)
. .
(4) G(S)=1,#}, {S→W#, W→0W0|1W1|# },S)u2192J|IBJ, B→0B|IB|(5) ε．, I→J|2|4|6|8, J→1|3|5|7|9},S)
(6)对应文法为 S→0A|1B|ε，A→0S|1C ， B→0C|1S， C→1A|0B
2-3 解：
nmn
|n,m≥0}。a0本文法构成的语言集为：L(G)={(10) ab(1)
nn+
，该语言特点是：产生的句子中，0、 |n≥0}(2) L(G)={110个数相同，并且若干相接的1后
必然紧接数量相同的连续的0。
pnnnnq
|q≥1,n≥0}，特点10|p≥1,n≥0}∪{100L(G)={1(3) 本文法构成的语言集为：
2n-1
mpnnnnqn
。00形
式，进一步，可知其具有形式{10|n,m≥0,且n+m>0} 是具有110或1 。L(G)={a|n≥1}可知，该语言特点是：产生的句子是奇数个a(4)由
2-4 证明： abc，它对应两个最右推导：因为存在句子： abc Abc S ? AB ?? abc S Dc ?? DC ? 所以，本文法具有二义性。 2-5 解： 的最右推导为：句子bbaacb bbaacb bbAacb bAacb Aacb AaSb AB S ??????
. .
上面推导中，下划线部分为
当前句型的句柄。 bbaacb与句子相应的语法树为：
(2)(3)SAb B(2)a (1)(1)2-5 (2)A b (2)Sc (1)b (1)A a 答案图 (3)
全部的短语为：一个 接短语）；S
(1)(1)
A→a）的短语（直) (产生式aa（）是句子bbaacb相对于非终结符A (A第 a是句子A的短语；bbaacb相对于非终结符b
(1)
(3)(2)(1)(1)
(2)(1)(1)
是句子bbabbaacb相对
于非终结符A的短语； （产生式S→c）的短语（直接短语）；bbaacbc是句子相对于非终结符
(3)(2)
的短语；bbaacb相对于非终结符Bcba是句子
(2)(3)(1)(2)(1)(2)
的短语；Scb是句子bbaacbbbaa相
对于非终结符 注：符号的上标是为了描述方便加上去的。
2-6 解：的产生BB(1) 因为由非终结符号推导不出终结符号串，因此是无用符号，含有B S→→→Bab式B,BcSB, aABS都是无用产生式，应予以删除。bAB和A→ 因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为c S→bCACdcCC A→cSA|C→cS|.
.
(2) 因为由文法的开始符号推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式C→cAB|dSD|a都是无用产生式，也应予以删除。
因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为 S→aAB|E A→dDA|e B→f D→eA E→fA|g
(3) 因为由非终结符号A,B推导不出终结符号串，因此A,B是无用符号，删除含有A,B的产生式S→Ba, A→cBC和B→SA后得到文法G′[S]: S→ac C→bC|d
又因为由文法G′[S]的开始符号S推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式C→bC|d都是无用产生式，也应予以删除。
因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法G〞[S]为 S→ac
2-7 解：
(1) 对于G，我们可得到W={A}；再按如下步骤得到产生式集P′： 对于产生式S→aAS，将产生式S→aAS及S→aS放入P′； 对于产生式S→b，直接将产生式S→b放入P′； 对于产生式A→cS，将产生式A→cS放入P′。 于是得到消除ε-产生式后的文法为： S→aAS|aS|b A→cS
(2) 对于G，我们可得到W={A}；再按如下步骤得到产生式集P′： 对于产生式S→aAA，将产生式S→aAA及S→Aa和S→a放入P′；
对于产生式A→bAc，将产生式A→bAc及A→bc放入P′； 对于产生式A→dAe，将产生式A→dAe及A→de放入P′。 于是得到消除ε-产生式后的文法为： S→aAA|aA|a A→bAc|bc|dAe|de
2-8 解：
(1) 首先求出如下集合
W(S)={S}, W(A)={A}, W(B)={B,C}, W(C)={C}, W(D)={D,B,C}
. .
然后按如下步骤得到产生式集P′： 将P中的所有非单产生式添加到P′中： S→aB|BC A→aA|c|aDb B→DB C→b
因为C∈W(B)，故将C的所有非单产生式的右部作为B-产生式的右部添加到P′中： B→b
因为B∈W(D)，故将B的所有非单产生式的右部作为D-产生式的右部添加到P′中： D→DB
因为C∈W(D)，故将C的所有非单产生式的右部作为D-产生式的右部添加到P′中： D→b
由此得到消除单产生式后的文法如下： S→aB|BC A→aA|c|aDb B→DB|b C→b D→b|DB
因为由文法的开始符号推导不出含有非终结符号A的句型，因此A是无用符号，含有A的产生式A→aA|c|aDb都是无用产生式，应予以删除。 于是得到消除无用产生式和单产生式后的文法如下： S→aB|BC B→DB|b C→b D→b|DB
(2) 首先求出如下集合
W(S)={S,A,B}, W(A)={A,B}, W(B)={B}
然后按如下步骤得到产生式集P′： 将P中的所有非单产生式添加到P′中： S→SA|SB A→(S)|( ) B→[S]|[ ]
因为A∈W(S)，故将A的所有非单产生式的右部作为S-产生式的右部添加到P′中： S→(S)|( )
. .
因为B∈W(S)，故将B的所有非单产生式的右部作为S-产生式的右部添加到P′中： S→[S]|[ ]
因为B∈W(A)，故将B的所有非单产生式的右部作为A-产生式的右部添加到P′中： A→[S]|[ ]
由此得到消除单产生式后的文法如下： S→SA|SB|(S)|( )|[S]|[ ] A→(S)|( )|[S]|[ ] B→[S]|[ ]
(3) 首先求出如下集合
W(E)={E,T,F,P}, W(T)={T,F,P}, W(F)={F,P}, W(P)={P}
然后按如下步骤得到产生式集P′： 将P中的所有非单产生式添加到P′中： E→E+T T→T*F F→P↑F P→(E)|i
因为T,F,P∈W(E)，故将T,F,P的所有非单产生式的右部作为E-产生式的右部添加到P′中： E→T*F E→P↑F E→(E)|i
因为F,P∈W(T)，故将F,P的所有非单产生式的右部作为T-产生式的右部添加到P′中： T→P↑F T→(E)|i
因为P∈W(F)，故将P的所有非单产生式的右部作为F-产生式的右部添加到P′中： F→(E)|i
由此得到消除单产生式后的文法如下： E→E+T|T*F|P↑F|(E)|i T→T*F|P↑F|(E)|i F→P↑F|(E)|i P→(E)|i
.
相关推荐：
loading