本书是理论计算机科学方面的经典教材，主要讨论形式语言与自动机理论、可计算性理论和计算复杂性理论等内容。本书强调定义和定理的准确性和严谨性，但在形式化证明中又非常注重符合直觉的理解，避免多余的数学细节。本书分为理论和应用两个部分：理论部分主要介绍有穷自动机、正则语言和文法、上下文无关语言和文法、下推自动机、图灵机、形式语言和自动机的层次结构以及计算复杂性等内容，应用部分主要介绍编译器和解析、LL解析以及LR解析。本书可帮助读者熟悉计算机科学的基础和原理，加强严格的形式化数学证明的能力，适合高等院校计算机科学及相关专业的学生学习，也适合理论计算机科学方向的研究人员参考。
理论部分
第 1 章 计算理论概论 2
1.1 数学预备知识和符号表示 3
1.2 三个基本概念 15
1.3 应用 * 27
第 2 章 有穷自动机 33
2.1 确定的有穷接受器 33
2.2 非确定的有穷接受器 44
2.3 确定与非确定的有穷接受器的等价性 51
2.4 减少有穷自动机中状态的化简 * 58
第 3 章 正则语言和正则文法 64
3.1 正则表达式. 64
3.2 正则表达式和正则语言的联系 70
3.3 正则文法 80
第 4 章 正则语言的性质 89
4.1 正则语言的封闭性 90
4.2 正则语言的基本问题 99
4.3 识别非正则语言 102
第 5 章 上下文无关语言 113
5.1 上下文无关文法 114
5.2 解析和歧义性 123
5.3 上下文无关文法和程序设计语言 132
第 6 章 上下文无关文法的化简和范式 135
6.1 文法转换的方法 136
6.2 两种重要的范式 149
6.3 上下文无关文法的成员资格判定算法 * 156
第 7 章 下推自动机 159
7.1 非确定的下推自动机 160
7.2 下推自动机和上下文无关语言 168
7.3 确定的下推自动机和确定的
7.4 确定的上下文无关语言的
第 8 章 上下文无关语言的性质 188
8.1 两个泵引理 188
8.2 上下文无关语言的封闭性
第 9 章 图灵机 204
9.1 标准的图灵机 204
9.2 完成复杂任务的组合图灵机 218
9.3 图灵论题 222
第 10 章 图灵机的其他模型 225
10.1 对图灵机的小改动 225
10.2 具有更复杂存储的图灵机 232
10.3 非确定的图灵机 236
点击下载