本书由计算理论领域的知名权威Michael Sipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。绝大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并对课堂测试题进行了全面的更新，每章末均有样例解答。

本书是计算理论领域的经典著作，被国外多所大学选用为教材。本书以注重思路、深入引导为特色，系统地介绍计算理论的三大主要内容：自动机与语言、可计算性理论和计算复杂性理论。同时，对可计算性和计算复杂性理论中的某些高级内容作了重点讲解。全书通过启发性的问题、精彩的结果和待解决问题来引导读者挑战此领域中的高层次问题。新版的一大亮点是增加了更多习题、教辅资料和部分习题解答，更加有利于教学。

全书叙述由浅入深、详略得当，重点突出，不拘泥于技术细节。可作为计算机专业高年级本科生和研究生的教材，也可作为相关专业教师和研究人员的参考书。

出版者的话

专家指导委员会

译者序

译者简介

第1版前言

第2版前言

第0章  绪论

 O．1 自动机、可计算性与复杂性

O．1．1计算复杂性理论

O．1．2可计算性理论

O．1．3 自动机理论

 O．2数学概念和术语

O．2．1集合

0．2．2序列和多元组

O．2．3函数和关系

O．2．4 图

O．2．5字符串和语言

O．2．6布尔逻辑

O．2．7数学名词汇总

 O．3定义、定理和证明

 O．4证明的类型

0．4．1构造性证明

O．4．2反证法

O．4．3归纳法

 练习

 问题

 习题选解

第一部分自动机与语言

第1章 正则语言

 1．1有穷自动机

1．1．1有穷自动机的形式化定义

1．1．2有穷自动机举例

1．1I 3计算的形式化定义

1．1．4设计有穷自动机

1．1．5 iE则运算

1．2非确定性

1．2．1非确定型有穷自动机的形式化

定义

1．2．2 NFA与DFA的等价性

1．2．3在正则运算下的封闭性

1．3正则表达式

1．3．1正则表达式的形式化定义

1．3．2与有穷自动机的等价性

1．4非正则语言

练习

问题

习题选解

第2章  上下文无关文法

2．1上下文无关文法概述

2．1．1上下文无关文法的形式化

定义

2．1．2上下文无关文法举例

2．1．3设计上下文无关文法

2．1I 4歧义性

2．1．5乔姆斯基范式

2．2下推自动机

2．2．1下推自动机的形式化定义

2．2．2下推自动机举例

2．2．3与上下文无关文法的等价性

  2．3非上下文无关语言

练习

问题

习题选解

第二部分 可计算性理论

第3章  丘奇一图灵论题

 3．1图灵机

3．1．1图灵机的形式化定义

3．1．2图灵机的例子

 3．2图灵机的变形

3．2．1多带图灵机

3．2．2非确定型图灵机

3．2．3枚举器

3．2．4与其他模型的等价性

 3．3算法的定义

3．3．1希尔伯特问题

3．3．2描述图灵机的术语

 练习

 问题

 习题选解

第4章  可判定性

 4．1可判定语言

4．1．1 与正则语言相关的可判定性问题

4．1．2 与上下文无关语言相关的可判定性问题

 4．2停机问题

4．2．1对角化方法

4．2．2停机问题是不可判定的

4．2．3一个图灵不可识别语言

 练习

 问题

 习题选解

第5章  可归约性

 5．1语言理论中的不可判定问题

 5．2一个简单的不可判定问题

 5．3映射可归约性

5．3．1可计算函数

5．3．2映射可归约性的形式定义

 练习

 问题

 习题选解

第6章  可计算性理论的高级专题

 6．1递归定理

6．1．1 自引用

6．1．2递归定理的术语

6．1．3应用

 6．2逻辑理论的可判定性

6．2．1一个可判定的理论

6．2．2一个不可判定的理论

 6．3图灵可归约性

 6．4信息的定义

6．4．1极小长度的描述

6．4．2定义的优化

6．4．3不可压缩的串和随机性

练习

问题

习题选解

第三部分复杂性理论

第7章  时间复杂性

 7．1度量复杂性

7．1．1大0和小o记法

7．1．2分析算法

7．1．3模型间的复杂性关系

 7．2 P类

7．2．1多项式时间

7．2．2 P中的问题举例

 7．3 NP类

7．3．1 NP中的问题举例

7．3．2 P与NP问题

 7．4 NP完全性

7．4．1多项式时间可归约性

7．4．2 NP完全性的定义

7．4．3库克一列文定理

 7．5几个NP完全问题

7．5．1顶点覆盖问题

7．5．2哈密顿路径问题

7．5．3子集和问题

 练习

 问题

 习题选解

第8章  空间复杂性

 8．1萨维奇定理

 8．2 PSPACE类

 8．3 PSPACE完全性

8．3．1 TQBF问题

8．3．2博弈的必胜策略

8．3．3广义地理学

 8．4 L类和NL类

 8．5 NL完全性

 8．6 NL等于coNL

 练习

 问题

 习题选解

第9章  难解性

 9．1层次定理

 9．2相对化

 9．3电路复杂性

 练习

 问题

 习题选解

第10章  复杂性理论高级专题

 10．1近似算法

 10．2概率算法

10．2．1 BPP类

10．2．2素数性

10．2．3只读一次的分支程序

 10．3交错式

10．3．1交错式时间与交错式空间

10．3．2多项式时间层次

 10．4交互式证明系统

10．4．1 图的非同构

10．4．2模型的定义

10．4．3 IP=PSPACE

 10．5并行计算

10．5．1一致布尔电路

10．5．2 NC类

10．5．3 P完全性

 10．6密码学

10．6．1密钥

1O．6．2公钥密码系统

10．6．3单向函数

10．6．4天窗函数

 练习

 问题

 习题选解

参考文献

索引