内 蒙 古 科 技 大 学
研究生考试试卷
成绩
考试科目： 形式语言与自动机理 阅 卷 人： 专 业： 学 号： 姓 名：
1、考前研究生将上述项目填写清楚； 2、字迹要清晰；
3、教师将试卷、答案一起送研究生学院归档。
年 月 日
《形式语言与自动机理论》试题
一、 试述正规文法、有穷自动机的概念，相互之间的关系作用。
二、 试述上下文无关文法、下推自动机的概念，相互之间的关系、作用。
三、 试述上下文有关文法、线性有界自动机的概念、相互之间的关系作用。
四试述短语级文法、图灵机的概念、相互之间的关系、作用。
五、查阅文献、找到文法、有穷自动机、下推自动机、线性有界自动机、图灵机或其他自动机在问题域建模中的应用实例分析。
答卷要求:
1. 打印该试卷和考试封面，并将封面钉在试卷首页 2. 认真填写封面，将阅卷人和成绩留空 3. 用A4白纸进行答卷
4. 将本试卷及答案于下周四（12月6日）集体交
5. 交卷的同时请在点名册上确认自己的学号的姓名，保证信息
无误。请同学们相互转告，尽量亲自前来交卷并确认信息 6. 第五题要求将参考论文打印并附在试卷后面；参考资料:《形
式语言与自动机理论》，蒋宗礼，清华大学出版社；相关文献、网络资源 7. 祝大家心情愉快！