内容发布更新时间 : 2024/12/29 23:46:18星期一 下面是文章的全部内容请认真阅读。

第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