形式语言与自动机理论（博士考试大纲）

1 计算机理论导引

1.1 三个基本概念

 1.1.1 D语言

 1.1.2 D文法

 1.1.3 自动机

1.2 一些应用

2 有穷自动机

2.1 确定型有穷自动机

2.2 非确定型有穷自动机

2.3 D确定型有穷自动机与非确定型有穷自动机的等价性

2.4 有穷自动机的化简

3 正则语言和正则文法

3.1 D正则表达式

3.2正则表达式与正则语言间的联系

3.3 D正则文法

4 正则语言的性质

4.1 正则语言的封闭性

 4.1.1 简单集合运算的封闭性

 4.1.2 其它运算的封闭性

4.2 正则语言的基本问题

4.3 识别非正则语言

 4.3.1 D使用鸽巢原理

 4.3.2 D泵引理

5 上下文无关语言

5.1 上下文无关文法

 5.1.1 D最左推导和最右推导

 5.1.2 D推导树

 5.1.3 句型与推导树的关系

5.2  分析与二义性

5.3 上下文无关文法和程序设计语言

6 上下文无关文法的化简与范式

6.1 文法变换方法

 6.1.1 删除无用产生式

 6.1.2 消除l产生式

 6.1.3 消除单一产生式

6.2 两个重要的范式

6.2.1 D乔姆斯基范式

6.2.2 格里巴克范式

7 下推自动机

7.1 非确定型下推自动机

 7.1.1 下推自动机的定义

 7.1.2 D下推自动机接受的语言

7.2 下推自动机与上下文无关语言

 7.2.1 上下文无关语言相应的下推自动机

 7.2.2 下推自动机相应的上下文无关语言

7.3 确定型下推自动机和确定型上下文无关语言

8 上下文无关文法的性质

8.1 D泵引理

8.2 上下文无关语言的封闭性和判定算法

 8.2.1 上下文无关语言的封闭性

 8.2.2 D上下文无关语言的可判定性质

9 图灵机

9.1 标准图灵机

 9.1.1 D图灵机的定义

 9.1.2 D作为语言接受器的图灵机

 9.1.3 作为转换器的图灵机

9.2 完成复杂任务的组合图灵机

9.3 图灵论题

10 算法计算的限制

10.1 图灵机所不能解决的问题

 10.1.1D 可计算性和可判定性

 10.1.2 图灵机停机问题

 10.1.3 将一个不可判定问题简化成另一个问题

10.2 递归可枚举语言的不可判定问题

10.3 上下文无关语言的不可判定问题

10.3 D图灵机与复杂性

10.4 语言族和复杂性类

10.5 复杂性类P和NP

主要参考教材：蒋宗礼 姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003.1