资源描述：
《编译原理答案29467》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章习题2-1设有字母表A1={a,b,c,…,z}，A2={0,1,…,9}，试回答下列问题：(1)字母表A1上长度为2的符号串有多少个？(2)集合A1A2含有多少个元素？(3)列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。2-2试分别构造产生下列语言的文法：（1）{anbn
2、n≥0}；（2）{anbmcp
3、n,m,p≥0}；（3）{an#bn
4、n≥0}∪{cn#dn
5、n≥0}；（4）{w#wr#
6、w∈{0,1}*,wr是w的逆序排列}；（5）任何不是以0打头的所有奇整数所组成的集合；（6）
7、所有由偶数个0和偶数个1所组成的符号串的集合。2-3试描述由下列文法所产生的语言的特点：（1）S→10S0S→aAA→bAA→a（2）S→SSS→1A0A→1A0A→ε（3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε（4）S→aSSS→a2-4试证明文法S→AB
8、DCA→aA
9、aB→bBc
10、bcC→cC
11、cD→aDb
12、ab为二义性文法。2-5对于下列的文法S→AB
13、cA→bA
14、aB→aSb
15、c试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。2-6化简
16、下列各个文法(1)S→aABS
17、bCACdA→bAB
18、cSA
19、cCCB→bAB
20、cSBC→cS
21、c(2)S→aAB
22、EA→dDA
23、eB→bE
24、fC→cAB
25、dSD
26、aD→eAE→fA
27、g(3)S→ac
28、bAA→cBCB→SAC→bC
29、d2-7消除下列文法中的ε-产生式(1)S→aAS
30、bA→cS
31、ε(2)S→aAAA→bAc
32、dAe
33、ε2-8消除下列文法中的无用产生式和单产生式(1)S→aB
34、BCA→aA
35、c
36、aDbB→DB
37、CC→bD→B(2)S→SA
38、SB
39、AA→B
40、(S)
41、()B→[S]
42、[](3)E
43、→E+T
44、TT→T*F
45、FF→P↑F
46、PP→(E)
47、i第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解：(1)对应文法为G(S)=({S},{a,b},{S→ε
48、aSb},S)(2)对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS
49、X,X→bX
50、Y,Y→cY
51、ε},S)(3)对应文法为G
52、(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb
53、#,Y→cYd
54、#},S)(4)G(S)=({S,W,R},{0,1,#},{S→W#,W→0W0
55、1W1
56、#},S)(5)G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J
57、IBJ,B→0B
58、IB
59、ε,I→J
60、2
61、4
62、6
63、8,J→1
64、3
65、5
66、7
67、9},S)(6)对应文法为S→0A
68、1B
69、ε，A→0S
70、1C，B→0C
71、1S，C→1A
72、0B2-3解：(1)本文法构成的语言集为：L(G)={(1
73、0)nabma0n
74、n,m≥0}。(2)L(G)={1n0n
75、n≥0}+，该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同的连续的0。(3)本文法构成的语言集为：L(G)={1p1n0n
76、p≥1,n≥0}∪{1n0n0q
77、q≥1,n≥0}，特点是具有1p1n0n或1n0n0q形式，进一步，可知其具有形式{1n0m
78、n,m≥0,且n+m>0}。(4)由L(G)={a2n-1
79、n≥1}可知，该语言特点是：产生的句子是奇数个a。2-4证明：因为存在句子：abc，它对应两个最右推导：S
80、ÞABÞAbcÞabcSÞDCÞDcÞabc所以，本文法具有二义性。2-5解：句子bbaacb的最右推导为：SÞABÞAaSbÞAacbÞbAacbÞbbAacbÞbbaacb上面推导中，下划线部分为当前句型的句柄。与句子bbaacb相应的语法树为：全部的短语为：第一个a（a(1)）是句子bbaacb相对于非终结符A(A(1))(产生式A→a）的短语（直接短语）；b(1)a(1)是句子bbaacb相对于非终结符A(2)的短语；b(2)b(1)a(1)是句子bbaacb相对于非终结符A(3)的短语；c是句子b
81、baacb相对于非终结符S(1)（产生式S→c）的短语（直接短语）；a(2)cb(3)是句子bbaacb相对于非终结符B的短语；b(2)b(1)a(1)a(2)cb(3)是句子bbaacb相对于非终结符S(2)的短语；注：符号的上标是为了描述方便加上去的。2-6解：(1)因为由非终结符号B推导不出终结符号串，因此B是无用符号，含有B的产生式B→Bab,B→cSB,S→aABS和A→bAB都是无用产生式，应予以删除
