计算理论是计算机科学的理论基础。本书介绍了计算理论最核心、最基本的内容，包括形式语言与自动机、可计算性和计算复杂性三大部分。全书共分七章，分别为：集合、关系和语言；有穷自动机；上下文无关语言；Turing机；不可判定性；计算机复杂性；NP完全性。本书突出了算法，从而使计算机专业的学生更易接受，也更有收益。本书适合作为计算机专业及数学专业本科生或研究生的教材，也可供从事计算机科学的教学与研究人员参考。

译者序

第一版序言

第二版序言

导言

第一章 集合、关系和语言

第二章 有穷自动机

第三章 上下文无关语言

第四章 Turing机

第五章 不可判定性

第六章 计算复杂性

第七章 NP完全性

中英对照名词索引

计算理论中的一个核心问题是用有穷的规定说明表示语言。自然，任何有穷语言通过穷举该语言中的所有字符串给出它的有穷表示。只有当考虑无穷语言时这个问题才成为有争论的。