第 1 页 共 5 页
福州大学软件学院 2007～2008 学年第一学期
《编译原理》课程 期末考试（A 卷）
参考答案与评分标准
一、 单项选择题（每小题 1 分，共 10 分）
1、D 2、B 3、A 4、A 5、B 6、A 7、D 8、 D 9、A 10、D
二、 填空分析题（每个空格 1 分，共 10 分）
1、可规约符号串，左部
2、从左到右进行分析，采用最右推导的逆过程即最左归约，不向前看输入字符
3、移进-规约，规约-规约
4、栈式，堆式
5、活动记录
三、 综合题（共 80 分）
1、设 ({ , },{ , }, , ,{ }}
M
xy ab f x y= 为一非确定的有限自动机，其中
f
定义如下：
(){
}
,,
f
xa xy= (,) {}
f
xb y
=
(,)fya
φ
= (,) {,}
f
yb x y
=
试构造相应的确定有限自动机 M'并最小化。(16 分)
解答：
(1)
先画出 NFA M 相应的状态图：(4 分)
(2)
用子集法构造状态转换矩阵：(3 分)
I Ia Ib
0 {x} 2 {x,y} 1 {y}
1 {y} 2 {x,y}
2 {x,y} 2 {x,y} 2 {x,y}
(3)
得到 M'=({0,1,2}, {a,b}, f, 0, {1,2})，其状态转换图如下：(4 分)
b
X Y
a a
b
b
b
0
2
1
a
b b
a,b
评论2