-
第
2
章
习题解答
1.
文法
G[S]
为：
S->Ac|aB
A->ab
B->bc
写出
L(G[S])<
/p>
的全部元素。
[
答案
]
S=>Ac=>abc
或
S=>aB=>abc
所以
L(G[S])={abc}
==============================================
2.
文法
G[N]
< br>为：
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 <
/p>
========================================
=======
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
< br>写出
L(G[Z])
的全部元素。
[
答案
]
Z=>aZb=>aaZbb=>aaa..Z...bbb=>
aaa..ab...bbb
L(G[Z])={a
n
b
n
|n>=1}
================================================ =====================
=========
< br>5.
给出语言
{a
n
b
n
c
m
|n>=1,m>=0}
的上下文无关文法。
[
分析
]
本题难度不大，
主要是考上下文无关文法的基本概念。
上下文无
关文法的基
本定义是：
A->
β
,A
∈
Vn
，
β
∈（
Vn
∪
Vt
）
*
，注意关键
问题是保证
a
n
b
n
的成立，
即“
a
与
b
的个数要相等”，为此，可以用一条形如
A->aAb|ab
的产生式即可解
决。
[
答案
]
构造上下文无关文法如下：
S->AB|A
A->aAb|ab
B->Bc|c
[
扩展
]
凡是诸如此类的题都应按此思路进行，
本题可做为一个基本代表。
基本思路
是这样的：
要求符合<
/p>
a
b
c
，因为<
/p>
a
与
b
要求个数
相等，所以把它们应看作一个整体单元进
行，而
c
m
做为另一个单位，初步产生式就应写为
S->AB
，其中
A
推出
a
n
b
n
，<
/p>
B
推
出
c
m
。因为
m
可为
0
，故上式进一步改写为
S->AB|A<
/p>
。接下来考虑
A,
凡是要求两
个终结符个数相等的问题，都应写为
A->aAb|ab
< br>形式，对于
B
就很容易写成
B-
>Bc|c
了。
========
==================================================
===========
=========
6
.
写一文法，使其语言是偶正整数集合。
要求：
(1)
允许
0
开头；
(2)
不允许
0
开头。
[
答案
] <
/p>
(1)
允许
0
开
头的偶正整数集合的文法
E->NT|G|SFM
T->NT|G
N->D|1|3|5|7|9
D->0|G
G->2|4|6|8
S->NS|
ε
F->1|3|5|7|9|G
M->M0|0
(2)
不允许
0
开头的
偶正整数集合的文法
E->NT|D
T->FT|G
n
n
m
N->D|1|3|5|7|9
D->2|4|6|8
F->N|0
G->D|0
====================
=================================================<
/p>
========
7.
已知文法
G
：
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|i
试给出下述表达式的推导及语法树
(1)i; (2)i*i+i (3)i+i*i (4)i+(i+i)
[
答案
]
(1)E=>T=>F=>i
(2)E=>E+T=>T+
T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i
(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i* F=>i+i*i
(4)E=>E+T=>T+T=>F+T=>i+T=>i+F
=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)
=>i+(i+T)=>i+(i+F)=>i+(i+i)
8 .
为句子
i+i*i
构造两棵语法树，从
而证明下述文法
G[<
表达式
>]
是二义的。
〈表达式〉
->
〈表达式〉〈运算符〉〈表达式〉
|(
〈表达式〉
)|i
〈运算符〉
->+|-|*|/
[
答案
]
可为句子
i+i*i
构造两个不同的最右推导
< br>:
最右推导
1
〈表达式〉
=>
〈表达式〉〈运算符〉〈表达
式〉
=>
〈表达式〉〈运算符〉
i
=>
〈表达式〉
* i
=>
〈表达式〉〈运算符〉〈表达式〉
* i
=>
〈表达式〉〈运算符〉
i *
i
=>
〈表达式〉
+ i * i
=> i + i * i
最右推导
2
〈表达式〉
=>
〈表达式〉〈运算符〉〈表达式〉
=>
〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式
>
=>
〈表达式〉〈运算符〉〈表达式〉〈运
算符〉
i
=>
〈表达式〉〈运算符〉〈表达式〉
* i
=>
〈表达式〉〈运算符〉
i * i
=>
〈表达式〉
+ i * i
=> i + i * i
所以，该文法是二义的。
=====
==================================================
==========
=====
9.
文法
G[S]
为：
S->Ac|aB
A->ab
B->bc
该文法是否为二义的？为什么？
[
答案
]
对于串
abc
(1)S=>Ac=>abc
-
-
-
-
-
-
-
-
-
上一篇：为什么笔记本需要启动修复才能打开
下一篇：编译原理课后答案(陈火旺)