DOC《习题 第3章 文法和语言》

习题 第3章 文法和语言 1.

写一文法,使其语言是偶整数集合. 2.写一文法,使其语言是偶整数集合,但不允许由0打头. 3.写一文法G,使得 L(G) = { ambn | m≥0, n≥1 } 4.写一文法G,使得 L(G) = { ambncp | m≥0, n≥0, p≥0 } 5.设有文法 G1:S → AaB S → a A → AB A → b A →ε B → bB B →ε 写一文法G2,使得 L(G1) = L(G2),并且G2不含空规则. 6.写一文法,使其语言是十位数不是0的整数集合. 7.写出以下文法G所定义的语言L(G). G:S → SaS S → b S → d 8.设有文法G1:S → Sab S → c S → d 将其改写成以下形式的文法G2,每条规则形如: V → xW 或V→y其中V和W为非终结符,x和y为终结符串. 9.设有文法G1:S → abcdB B → efgB B → b 将其改写成以下形式的3型文法G2,每条规则形如: V → pW 或V→q其中V和W为非终结符,p和q为终结符. 10.设有文法G1:S → aBBaS B → bbAA A → aAbBc A → a 将其改写成以下形式的文法G2,每条规则形如: V → pX1X2…Xn 或V→q其中V和Xi为非终结符,p和q为终结符. 11.已知C语言的下标变量形如: a[E][E]…[E] 按第10题要求的文法G2的形式写出下标变量文法. 12.设有文法G1:S → aBcA S → aBdB A → bA A → aB B → Bd B → a 将其改写成文法G2,使得对每个非终结符均无两个不同规则能导出相同的终结开头符. 13.设有文法G:S → aBbD B → bSD B → aDa B → bb D → aBD 证明L(G)为空语言. 14.设有文法G1:S → 0Y | 1X | 1Y | 1S |ε X → 1Y | 1S |ε Y → 1Z Z → 1S |ε 将其改写成不含空规则的文法G2,且L(G1) = L(G2)∪{ε}. 15.设有文法 G:E → E+T | T T → T*F | F F → i | (E) (1)构造句子(i*i+i)*i的语法树,并写出该句子的规范推导过程;

(2)构造句型F*(T+i)+i的语法树,并求出该句型的所有短语、简单短语和句柄. 16.构造一个二义性文法. 17.教材3.14题18.教材3.16题