教学目标：
为了适应计算机科学技术的迅速发展和对系统研发人才的要求，计算机科学与技术和软件工程等专业的研究生有必要在深入学习专业知识的同时，对形式语言与自动机有一个全面的了解，以便掌握形式语言与自动机的两个必要组成部分：语言的形式化表示和自动机模型。
本课程的内容不仅含有有关正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识，更涉及到本学科方法论中所包含的3个学科形态。通过本课程的学习，培养学生的形式化描述、抽象思维、从实例计算到模型计算的能力，使学生掌握“问题-形式化-自动化（计算机化）”方法，为以后的研究做好准备。

课程内容：
1  计算机理论导引（2学时）
1.1 三个基本概念
1.1.1语言*
1.1.2 文法*
1.1.3 自动机
1.2 一些应用
2  有穷自动机（4学时）
2.1 确定型有穷自动机*
2.2非确定型有穷自动机*
2.3 确定型有穷自动机与非确定型有穷自动机的等价性#
2.4 有穷自动机的化简
3  正则语言和正则文法（2学时）
3.1 正则表达式*
3.2正则表达式与正则语言间的联系
3.3正则文法*
4  正则语言的性质（4学时）
4.1 正则语言的封闭性
4.1.1 简单集合运算的封闭性
4.1.2 其它运算的封闭性
4.2 正则语言的基本问题
4.3 识别非正则语言
4.3.1使用鸽巢原理*
4.3.2泵引理* #
5  上下文无关语言（2学时）
5.1 上下文无关文法
5.1.1 最左推导和最右推导*
5.1.2推导树*
5.1.3 句型与推导树的关系
5.2  分析与二义性
5.3 上下文无关文法和程序设计语言
6  上下文无关文法的化简与范式（4学时）
6.1 文法变换方法*
6.1.1 删除无用产生式
6.1.2 消除?产生式
6.1.3 消除单一产生式
6.2 两个重要的范式
6.2.1 ?乔姆斯基范式* #
6.2.2 格里巴克范式* #
7  下推自动机（4学时）
7.1 非确定型下推自动机
7.1.1 下推自动机的定义
7.1.2下推自动机接受的语言*
7.2 下推自动机与上下文无关语言
7.2.1 上下文无关语言相应的下推自动机*
7.2.2 下推自动机相应的上下文无关语言*
7.3 确定型下推自动机和确定型上下文无关语言#
8  上下文无关文法的性质（2学时）
8.1泵引理* #
8.2 上下文无关语言的封闭性和判定算法
8.2.1 上下文无关语言的封闭性
8.2.2 上下文无关语言的可判定性质*#
9  图灵机（2学时）
9.1 标准图灵机
9.1.1 图灵机的定义*
9.1.2 作为语言接受器的图灵机* #
9.1.3 作为转换器的图灵机*
9.2 完成复杂任务的组合图灵机* #
9.3 图灵论题●
10  算法计算的限制（4学时）
10.1 图灵机所不能解决的问题* #
10.1.1 可计算性和可判定性* #
10.1.2 图灵机停机问题* #
10.1.3 将一个不可判定问题简化成另一个问题* #
10.2 递归可枚举语言的不可判定问题
10.3 上下文无关语言的不可判定问题
10.3 图灵机与复杂性* #
10.4 语言族和复杂性类
10.5 复杂性类P和NP #

适用学生：
全日制硕士    非全日制硕士    留学硕士    进修硕士    硕博连读    本科直博    全日制博士    留学博士    进修博士    在职专硕    其他    

预修课程：
预修课程；
离散数学、高等数学

参考书目：
教材：朱保平,李千目.形式语言与自动机.北京：清华大学出版社，2015.
参考书：
Kamala Krithivasan Rama R著. 孟宇龙，等译.形式语言，自动机理论与计算导论.北京：电子工业出版社，2012.
必读参考资料：
Peter Linz箸,孙家彇等译.形式语言与自动机导论.北京：机械工业出版社，2005.

备注：