第2章形式语言
1．试分别构造产生下列语言的文法：
（1）{a n#b n|n≥0}∪{c n#d n|n≥0}；
（2）任何不是以0打头的所有奇整数所组成的集合。

答：(1) 对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X, S→Y, X→aXb|#, Y→cYd|# },S)
(2) G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},
{S→J|IBJ, B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S)
2．对于下列的文法
S→AB|c A→bA|a B→aSb|c
试给出句子bbaacb的最右推导。

答：S=>AB=>AaSb=> Aacb=>bAacb=>bbAacb=>bbaacb
3．已知文法G[S]: S->(AS)|(b)
A->(SaA)|(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)
直接短语：(SaA)，(b)
句柄：(SaA)
S
( A S )
( A S )
( S a A ) ( b )
4．试描述由下列文法所产生的语言的特点：
（1）S→10S0 S→aA A→bA A→a
（2）S→aSS S→a
答：(1) 本文法构成的语言集为：L(G)={(10)n ab m a0n|n,m≥0}。

(2)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。

附加题：试证明文法
S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab
为二义性文法。

答：因为存在句子：abc，它对应两个最右推导：
S ⇒ AB ⇒ Abc ⇒ abc
S ⇒ DC ⇒ Dc ⇒ abc
所以，本文法具有二义性。