习题第3章文法和语言
1．写一文法，使其语言是偶整数集合，但不允许由0打头。3．写一文法G，使得L(G) = { a m b n| m≥0, n≥1 }
4．写一文法G，使得L(G) = { a m b n c p| 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…X n
或V → q
其中V和X i为非终结符，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. 课本P49. 第14题（1）（2）
18. 课本P49. 第16题（2）
