第2章 习题解答 1.文法G[S]为：
S->Ac|aB A->ab B->bc
写出L(G[S])的全部元素。 [答案]
S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc}
============================================== 2. 文法G[N]为：
N->D|ND
D->0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ [答案]
G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D =============================================== 3.已知文法G[S]：
S→dAB A→aA|a B→ε|bB
问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？ [答案]
正规式是daa*b*；
相应的正规文法为(由自动机化简来)：
G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b
也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε
=============================================================================== 4.已知文法G[Z]：
Z->aZb|ab
写出L(G[Z])的全部元素。 [答案]
Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={anbn|n>=1}
==============================================================================
5.给出语言{anbncm|n>=1,m>=0}的上下文无关文法。 [分析]
本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A->β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题是保证anbn的成立，即“a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。 [答案]
构造上下文无关文法如下： S->AB|A A->aAb|ab B->Bc|c [扩展]
凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路是这样的：
要求符合abc，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而cm做为另一个单位，初步产生式就应写为S->AB，其中A推出anbn，B推出cm。因为m可为0，故上式进一步改写为S->AB|A。接下来考虑A,凡是要求两个终结符个数相等的问题，都应写为A->aAb|ab形式，对于B就很容易写成B->Bc|c了。
==============================================================================
6 .写一文法，使其语言是偶正整数集合。 要求：
(1)允许0开头； (2)不允许0开头。 [答案]
(1)允许0开头的偶正整数集合的文法
E->NT|G|SFM T->NT|G N->D|1|3|5|7|9 D->0|G G->2|4|6|8 S->NS|ε F->1|3|5|7|9|G M->M0|0
(2)不允许0开头的偶正整数集合的文法
E->NT|D T->FT|G
n
nm