习题第3章文法和语言参考答案
1．写一文法，使其语言是偶整数集合。
解：允许以0打头
G：N→+A|-A|A
A→DA|E
D→0|1|2|3|4|5|6|7|8|9
E→0|2|4|6|8
2．写一文法，使其语言是偶整数集合，但不允许由0打头。
解：0除外
G：N→+A|-A|A
A→CB|E
B→DB|E
C→1|2|3|4|5|6|7|8|9
D→0|1|2|3|4|5|6|7|8|9
E→0|2|4|6|8
3．写一文法G，使得L(G) = { a m b n| m≥0, n≥1 }
解：G1:S→aS|T或 G2:S→aS|bT 或 G3:S→aS|Sb|b
T→bT|b T→bT|ε
4．写一文法G，使得L(G) = { a m b n c p| m≥0, n≥0, p≥0 }
解：G1:S→ABC 或G2:S→Sc|T 或 G3:A→aA|bB|cC|εA→aA|ε T→Tb|R B→bB|cC|ε
B→bB|ε R→Ra|ε C→cC|ε
C→cC|ε
5．设有文法G1：S → AaB
S → a
A → AB
A → b
A →ε
B → bB
B →ε
写一文法G2，使得L(G1) = L(G2)，并且G2不含空规则。
解：G2:S→BaB|Ba|aB|a 或G2:S→bB|Sb|a
B→bB|b
6．写一文法，使其语言是十位数不是0的整数集合。
解：G：N→SA
S→+|-|ε
A→D|CD|BCD
B→B D|C
C→1|2|3|4|5|6|7|8|9
D→0|1|2|3|4|5|6|7|8|9
7．写出以下文法G所定义的语言L(G)。
G：S → SaS
S → b
S → d
解：L(G)={(xa)n x|n≥0, x∈{b,d}}
={((b|d)a)n(b|d)|n≥0}
={(b|d)(a(b|d))n|n≥0}
8．设有文法G1：S → Sab | c | d
将其改写成以下形式的文法G2，每条规则形如：
V → xW
或V → y
其中V和W为非终结符，x和y为终结符串。
解：G：S→cT|dT|c|d
T→abT|ab
9．设有文法G1：S → abcdB
B → efgB
B → b
将其改写成以下形式的3型文法G2，每条规则形如：
V → pW
或V → q
其中V和W为非终结符，p和q为终结符。
解：G：S→aA
A→bB
B→cC
C→dD
D→eE|b
E→fF
F→gD
10．设有文法G1：S → aBBaS
B → bbAA
A → aAbBc
A → a
将其改写成以下形式的文法G2，每条规则形如：
V → pX1X2…X n
或V → q
其中V和X i为非终结符，p和q为终结符。
解：G：S→aBBPS
P→a
B→bQAA
Q→b
A→aAQBR|a
R→c
11．已知C语言的下标变量形如：
a[E][E]…[E]
按第10题要求的文法G2的形式写出下标变量文法。
解：G：S→aA
A→[EB
B→]A
B→]
12．设有文法G1：S → aBcA
S → aBdB
A → bA
A → aB
B → Bd
B → a
将其改写成文法G2，使得对每个非终结符均无两个不同规则能导出相同的终结开头符。
解：G2：S→aB|P
P→cA|dB
A→bQ
Q→A|B
B→aD
D→dD|ε
13．设有文法G：S → aBbD
B → bSD
B → aDa
B → bb
D → aBD
证明L(G)为空语言。
解：∵D的唯一规则是无穷递归的，也就是无用规则
又∵开始符S的唯一规则含有D，也是无用规则
∴文法G的规则全是无用规则
故L(G)为空语言。
14．设有文法G1：S → 0Y | 1X | 1Y | 1S |ε
X → 1Y | 1S |ε
Y → 1Z
Z → 1S |ε
将其改写成不含空规则的文法G2，且L(G1) = L(G2)∪{ε}。
解：G2：S→0Y|1X|1Y|1S|1
X→1Y|1S|1
Y→1Z|1
Z→1S|1
15．设有文法 G ：E → E+T | T T → T*F | F F → i | (E)
（1）构造句子(i*i+i)*i 的语法树，并写出该句子的规范推导过程；
（2）构造句型F*(T+i)+i 的语法树，并求出该句型的所有短语、简单短语和句柄。 解：(1) 句子(i*i+i)*i 的语法树 规范推导过程：
E =〉T =〉T*F
=〉T*i
=〉F*i
=〉(E)*i
=〉(E+T)*i
=〉(E+F)*i
=〉(E+i)*i
=〉(T+i)*i
=〉(T*F+i)*i
=〉(T*i+i)*i
=〉(F*i+i)*i
=〉(i*i+i)*i
(2) 句型F*(T+i)+i 的语法树 短语 简单短语 句柄
F*(T+ i 1)+ i 2 F*(T+ i 1)
F F F
(T+ i 1)
T+ i 1
T T
i 1 i 1 i 2 i 2
E
* T F E ( ) F T i + E T T * T F F i
i F i E
+ E T *
T F T F T
E ( )
F i 2 F
+ E T i 1
