编译原理第二章(2-构造文法)

第二章 高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。

（2） 优先顺序为↑，+，*，同级优先采用右结合。

解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为 N →D|NDD →0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L （G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。

解：（1）L （G6）=｛a|a ∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N ＝＞ND ＝＞ NDD ＝＞ NDDD ＝＞ DDDD ＝＞ 0DDD ＝＞ 01DD ＝＞ 012D ＝＞ 0127 N ＝＞ ND ＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N ＝＞ ND ＝＞ DD ＝＞ 3D ＝＞ 34 N ＝＞ ND ＝＞ N4＝＞ D4 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →1|3|5|7|9, M →MB|1|2|3|4|5|6|7|8|9 B →0|1|2|3|4|5|6|7|8|9 8. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。

第一章练习题（绪论）一、选择题1．编译程序是一种常用的软件。

A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序是可执行程序。

A) 一定B) 不一定3．编译程序的大多数时间是花在上。

A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。

A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。

5．编译程序各个阶段都涉及到的工作有。

A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。

A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。

A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于。

A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于。

A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。

10．编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题1．文法 G 产生的 (1) 的全体是该文法描述的语言。

A.句型B. 终结符集C. 非终结符集D. 句子2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C)文法；2 型语言可由(G) 识别。

A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。

第二章文法和语言本章讲述目前广泛使用的上下文无关文法。

即用上下文无关文法作为程序设计语言语法的描述工具。

阐明语法的一个工具是文法。

本章将介绍文法和语言的概念。

本章重点：上下文无关文法及其句型分析中的有关问题。

第一节文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。

是汉语的一个句子。

汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：〈句子〉∷＝〈主语〉〈谓语〉〈主语〉∷＝〈代词〉|〈名词〉〈代词〉∷＝我|你|他〈名词〉∷＝王明|大学生|工人|英语〈谓语〉∷＝〈动词〉〈直接宾语〉〈动词〉∷＝是|学习〈直接宾语〉∷＝〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。

这些规则成为我们判别句子结构合法与否的依据。

一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。

我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉⇒〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。

比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉⇒〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：〈句子〉⇒〈主语〉〈谓语〉⇒〈代词〉〈谓语〉⇒我〈谓语〉⇒我〈动词〉〈直接宾语〉⇒我是〈直接宾语〉⇒我是〈名词〉⇒我是大学生符号⇒的含义是，使用一条规则，代替⇒左边的某个符号，产生⇒右端的符号串。

显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。

第2章习题解答1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2.文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D……D3.已知文法G[S]:Sf dAB Af 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...bbbL(G[Z])={a n b n|n>=1}5.给出语言｛a n b n c1 n>=1,m>=0｝的上下文无关文法。

［分析］本题难度不大，主要是考上下文无关文法的基本概念。

上下文无关文法的基本定义是：A-> B ,A € Vn ,B€( VnU Vt) *,注意关键问题是保证a n b n的成立，即“ a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。

［答案］构造上下文无关文法如下：S->AB|AA->aAb|abB->Bc|c［扩展］凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。

基本思路是这样的：要求符合a n b n c m，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而c m做为另一个单位，初步产生式就应写为S->AB,其中A推出a n b n，B推出c m。

第二章 词法分析2.1 完成下列选择题：(1) 词法分析器的输出结果是。

a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值(2) 正规式M1和M2等价是指。

a. M1和M2的状态数相等b. M1和M2的有向边条数相等c. M1和M2所识别的语言集相等d. M1和M2状态数和有向边条数相等(3) DFA M(见图2-1)接受的字集为。

a. 以0开头的二进制数组成的集合b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合d. 含偶数个0的二进制数组成的集合【解答】(1) c (2) c (3) d图2-1 习题2.1的DFA M2.2 什么是扫描器？扫描器的功能是什么？【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。

每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下：f(x,a)={x,y} f {x,b}={y}f(y,a)=Φ f{y,b}={x,y}试构造相应的确定有限自动机M ′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题2.3的NFA M 用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

表2-2 状态转换矩阵将图2-3所示的DFA M ′最小化。

编译原理习题参考答案第⼆章2.构造产⽣下列语⾔的⽂法（2）{a n b m c p|n,m,p≥0}解： G(S) ：S→aS|X,X→bX|Y,Y→cY|ε（3）{a n # b n|n≥0}∪{cn # dn|n≥0}解： G(S)：S→X,S→Y,X→aXb|#, Y→cYd|# }（5）任何不是以0 打头的所有奇整数所组成的集合解：G(S)：S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8, J→1|3|5|7|9}（6）（思考题）所有偶数个0 和偶数个1 所组成的符号串集合解：对应⽂法为 S→0A|1B|ε，A→0S|1C B→0C|1S C→1A|0B3.描述语⾔特点（2）S→SS S→1A0 A→1A0 A→ε解：L(G)={1n10n11n20n2… 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm 不全为零}该语⾔特点是：产⽣的句⼦中，0、1 个数相同，并且若⼲相接的1 后必然紧接数量相同连续的0。

（5）S→aSS S→a解：L(G)={a(2n-1)|n≥1}可知：奇数个a5. (1) 解：由于此⽂法包含以下规则：AA→ε，所以此⽂法是0 型⽂法。

7.解：(1)aacb 是⽂法G[S]中的句⼦，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（3）aacbccb 不是⽂法G[S]中的句⼦aacbccb 不能从S推导得到时，它仅是⽂法G[S]的⼀个句型的⼀部分，⽽不是⼀个句⼦。

11.解：最右推导:(1) S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上⾯推导中，下划线部分为当前句型的句柄。

对应的语法树为：3 假设M:⼈ W:载狐狸过河，G:载⼭⽺过河，C:载⽩菜过河6 根据⽂法知其产⽣的语⾔是L={a m b n c i| m,n,i≧1}可以构造如下的⽂法VN={S,A,B,C}, VT={a,b,c}P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c} 其状态转换图如下:7 (1) 其对应的右线性⽂法是:A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2) 最短输⼊串011(3) 任意接受的四个串： 011,0110,0011,000011(4) 任意以1 打头的串.9．对于矩阵(iii)(1) 状态转换图：(2) 3型⽂法（正规⽂法）S→aA|a|bB A→bA|b|aC|a B→aB|bC|b C→aC|a|bC|b(3)⽤⾃然语⾔描述输⼊串的特征以a 打头，中间有任意个（包括0个）b,再跟a,最后由⼀个a,b 所组成的任意串结尾或者以b 打头，中间有任意个（包括0个）a,再跟b,最后由⼀个a,b 所组成的任意串结尾。

第一章练习题（绪论）一、选择题1．编译程序是一种常用的软件。

A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序是可执行程序。

A) 一定B) 不一定3．编译程序的大多数时间是花在上。

A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。

A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。

5．编译程序各个阶段都涉及到的工作有。

A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。

A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。

A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于。

A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于。

A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。

10．编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题1．文法 G 产生的 (1) 的全体是该文法描述的语言。

A.句型B. 终结符集C. 非终结符集D. 句子2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C)文法；2 型语言可由(G) 识别。

A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。

第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）{a n b n|n≥0}；（2）{a n b m c p|n,m,p≥0}；（3）{a n#b n|n≥0}∪{c n#d n|n≥0}；（4）{w#w r# | w∈{0,1}*,w r是w的逆序排列}；（5）任何不是以0打头的所有奇整数所组成的集合；（6）所有由偶数个0和偶数个1所组成的符号串的集合。

2-3 试描述由下列文法所产生的语言的特点：（1）S→10S0S→aA A→bA A→a（2）S→SS S→1A0A→1A0A→ε（3）S→1A S→B0A→1A A→CB→B0B→C C→1C0C→ε（4）S→aSS S→a2-4 试证明文法S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab为二义性文法。

2-5 对于下列的文法S→AB|c A→bA|a B→aSb|c试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。

2-6 化简下列各个文法(1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c(2) S→aAB|E A→dDA|e B→bE|fC→c AB|dSD|a D→eA E→fA|g(3) S→ac|bA A→c BC B→SA C→bC|d2-7 消除下列文法中的ε-产生式(1) S→aAS|b A→cS|ε(2) S→aAA A→bAc|dAe|ε2-8 消除下列文法中的无用产生式和单产生式(1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B(2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ](3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|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→ε| aSb },S)(2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε },S)(3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#,Y→cYd|# },S)(4) G(S)=({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)(5) 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)(6)对应文法为S→0A|1B|ε，A→0S|1C，B→0C|1S，C→1A|0B2-3 解：(1) 本文法构成的语言集为：L(G)={(10)n ab m a0n|n,m≥0}。

第2章形式语言的基本知识习题答案第 1 题文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第 2 题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案: 允许0 开头的非负整数或者G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}第3题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，7等构造一个文法。

答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第 4 题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。

答案：L(G[Z])={a n b n|n>=1}第 5 题（答案不唯一）写一文法，使其语言是偶正整数的集合。

要求：(1) 允许0 打头；(2)不允许0 打头。

答案：(1)允许 0 开头的偶正整数合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许 0 开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第 6 题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的最左推导及语法树。

（1）i+(i+i)（2）i+i*i答案：(1) <表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）(2) <表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i第7 题为句子i+i*i 构造两棵语法树，从而证明下述文法G[〈表达式〉]是二义的。

第二章部分习题答案2.1 考虑文法S→S S + | S S * | aa)证明文法可生成符号串 a a + a *解：S→S S * →S S + S * →a S + S * → a a + S *→ a a + a *b)为此符号串构造语法树解：c)文法生成什么样的语言？证明结论解：将a看作运算数，文法生成语言L={支持加法、乘法的表达式的后缀表示形式} 证明类似2.2题b)＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝2.2 下列文法生成什么样的语言？证明你的结论。

是否有二义性？a)S →0 S 1 | 0 1解：生成语言L={0n1n | n>=1}证明：1) 证文法推导出的符号串都在L中i)考虑最小语法树，推导出的符号串01显然∈Lii)假定结点数<n的语法树对应的符号串都∈L，考虑结点数=n的语法树S，其结构必为，子树S1结点数<n，因此对应符号串t1∈L，S对应符号串为t=0 t1 1，因此t∈L综合i)、ii)，1)得证2) 证L中符号串都可由文法推导出i)L中最短符号串01，显然可由文法推导出ii)假定L中长度<2n的符号串都可由文法推导出，考虑长度=2n的符号串t＝0n1n，它可表示为0 t1 1，t1∈L且长度<2n ，因此它可被文法推导出，对应语法树，构造语法树，显然，它的输出为t，即t可被文法推导出综合i)、ii)，2)得证综合1)、2)，文法生成的语言即为L另外，文法没有二义性＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝b)S →+ S S | - S S | a解：生成语言L={支持加法、减法的表达式的前缀表示形式}证明：1) 证文法推导出的符号串都在L中i)考虑最小语法树，推导出的符号串a显然∈Lii)假定结点数<n的语法树对应的符号串都∈L，考虑结点数=n的语法树S ，其结构必为，子树S1、S2结点数<n，因此对应符号串E1、E2∈L（前缀表达式），S对应符号串为E=+/- E1 E2，E也是前缀表达式。

第2章习题解答1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素。

[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}==============================================2. 文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[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...bbbL(G[Z])={a n b n|n>=1}===================================================================== =========5.给出语言{a n b n c m|n>=1,m>=0}的上下文无关文法。