资源描述：
《编译原理形式语言题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章形式语言1．试分别构造产生下列语言的文法：（1）{an#bn
2、n≥0}∪{cn#dn
3、n≥0}；（2）任何不是以0打头的所有奇整数所组成的集合。答：(1)对应文法为G(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb
4、#,Y→cYd
5、#},S)(2)G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J
6、IBJ,B→0B
7、IB
8、ε,I→J
9、2
10、4
11、6
12、8,J→1
13、3
14、5
15、7
16、9},S)2．对于下列的文法S→AB
17、cA→bA
18、aB→aSb
19、c试给出句子bb
20、aacb的最右推导。答：S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb3．已知文法G[S]:S->(AS)
21、(b)A->(SaA)
22、(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。答：因为S不能Þ(a),所以(a)不是文法的句型。没有短语、直接短语和句柄。因为SÞ(AS)Þ(A(AS))Þ(A((SaA)S))Þ(A((SaA)(b))),所以(A((SaA)(b)))是文法的句型。短语：(A((SaA)(b)))，((SaA)(b))，(SaA)，(b)直接
23、短语：(SaA)，(b)句柄：(SaA)S(AS)(AS)(SaA)(b)4．试描述由下列文法所产生的语言的特点：（1）S→10S0S→aAA→bAA→a（2）S→aSSS→a答：(1)本文法构成的语言集为：L(G)={(10)nabma0n
24、n,m≥0}。(2)由L(G)={a2n-1
25、n≥1}可知，该语言特点是：产生的句子是奇数个a。附加题：试证明文法S→AB
26、DCA→aA
27、aB→bBc
28、bcC→cC
29、cD→aDb
30、ab为二义性文法。答：因为存在句子：abc，它对应两个最右推导：SÞABÞAbcÞabcSÞDCÞDc
31、Þabc所以，本文法具有二义性。
