计算理论导引（原书第3版）

　　目录
　　Introduction to the Theory of Computation,3e
　　出版者的话
　　译者序
　　第3版前言
　　第2版前言
　　第1版前言
　　第0章绪论
　　0.1自动机、可计算性与复杂性
　　0.1.1计算复杂性理论
　　0.1.2可计算性理论
　　0.1.3自动机理论
　　0.2数学概念和术语
　　0.2.1集合
　　0.2.2序列和多元组
　　0.2.3函数和关系
　　0.2.4图
　　0.2.5字符串和语言
　　0.2.6布尔逻辑
　　0.2.7数学名词汇总
　　0.3定义、定理和证明
　　0.4证明的类型
　　0.4.1构造性证明
　　0.4.2反证法
　　0.4.3归纳法
　　练习
　　问题
　　习题选解
　　第一部分自动机与语言
　　第1章正则语言
　　1.1有穷自动机
　　1.1.1有穷自动机的形式化定义
　　1.1.2有穷自动机举例
　　1.1.3计算的形式化定义
　　1.1.4设计有穷自动机
　　1.1.5正则运算
　　1.2非确定性
　　1.2.1非确定型有穷自动机的形式化定义
　　1.2.2NFA与DFA的等价性
　　1.2.3在正则运算下的封闭性
　　1.3正则表达式
　　1.3.1正则表达式的形式化定义
　　1.3.2与有穷自动机的等价性
　　1.4非正则语言
　　练习
　　问题
　　习题选解
　　第2章上下文无关文法
　　.......

　　《计算理论导引（原书第3版）》由计算理论领域的知名MichaelSipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。