内容发布更新时间 : 2024/12/22 19:41:58星期一 下面是文章的全部内容请认真阅读。

第3章 文法和语言

第1题

文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc

写出L(G[S])的全部元素。 答案：

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 或者：允许0开头的非负整数？

第３题

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。 答案：

G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9

第4题

已知文法G[Z]： Z→aZb|ab

写出L(G[Z])的全部元素。 答案：

Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb

L(G[Z])={ab|n>=1}

第5题

写一文法，使其语言是偶正整数的集合。 要求： (1) 允许0打头；

(2)不允许0打头。 答案：

(1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8

(2)不允许0开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题

nn

已知文法G：

<表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i

试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i

第8题

文法G[S]为： S→Ac|aB A→ab B→bc

该文法是否为二义的？为什么？ 答案：

对于串abc

(1)S=>Ac=>abc (2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。 或者：

第10题

文法S→S(S)S|ε

(1) 生成的语言是什么？

(2) 该文法是二义的吗？说明理由。

答案：

（１） 嵌套的括号

（２） 是二义的，因为对于（）（）可以构造两棵不同的语法树。

第11题

令文法G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。