文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答
侵权投诉

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

合肥工业大学 试卷 编译原理

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

20~20学年第学期 课程代码课程名称学分课程性质:必修

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

限修

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

考试形式:开卷

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

专业班级(教学班) 考试日期

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

命题教师 系(所或教研室)主任审批签名 张炳武

一、 给出识别正规式 (00|11)*(01*|10*)的极小化的确定有限状态自动机。(10分)

参考解答:

本题考查识别给定正规式(集)的NFA的构造及其确定化和极小化的过程。 识别该正规式的一种NFA如下:

然后根据子集构造法将上述NFA确定化,如下:

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

评分:给出正确形式的NFA,得5分;给出正确极小化过程给2分;最终DFA正确,给3分。

二、根据题一的结果,写一个上下文无关文法,它产生和题一中的正规集相同的语言。 (10分)

参考解答:

本题考查由FA构造识别同样正规集的上下文无关文法的过程。 上下文无关文法如下:

A 0 B | 1 C B 0 A | 1 D C 1 A | 0 E D 1 D | ε E 0 E | ε

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

评分:每给出一个正确产生式,得1分,其中A~E名字可以任意命名。

三、下面是识别G1 LR(1)活前缀的FA。请将其补充完整,并给出在分析栈上串baba$的LR(1)分析过程。 (15分)

经过DFA极小化,仍为5个状态;即,最终结果为:

文法G1(0)S’ S(1)S BB(2)B bB(3)B a

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

2011-2012学年第一学期合肥工业大学软件学院编译原理试卷 - 试题解答

参考解答:

本题考查识别文法活前缀的FA的构造过程及移进-归约过程。

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email