本书是由John E.Hopcroft、Rajeev Motwani和Jeffrey D.Ullman三位计算机学者合作编写的，是最著名的理论计算机科学著作之一，是世界各国广泛采用的计算机理论专业和计算计工程专业的优秀教材之一。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书适合作为国内高校计算机高年级本科生或研究生的教材，还可供从事理论计算工作的研究人员参考。

本书是关于形式语言、自动机理论和计算复杂性方面的经典之作，是国际上得到广泛认可的计算机理论和计算机工程专业的优秀教材。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书注重定义、定理的准确性和严格性，注重学生形式化和严格的数学推理能力的培养，同时在定义和证明中运用直观的方法说明抽象概念，借助许多图表帮助传达思想，并包含大量难度各异的示例和习题，便于读者加深对内容的理解。

本书适合作为计算机专业高年级本科生及研究生计算理论课程的教材和教学参考书。

出版者的话

译者序

前言

第1章 自动机：方法与体验

 1.1 为什么研究自动机理论

1.1.1 有穷自动机简介

1.1.2 结构表示法

1.1.3 自动机与复杂性

 1.2 形式化证明简介

1.2.1 演绎证明

1.2.2 求助于定义

1.2.3 其他定理形式

1.2.4 表面上不是“如果-则”命题的定理

 1.3 其他的证明形式

1.3.1 证明集合等价性

1.3.2 逆否命题

1.3.3 反证法

1.3.4 反例

 1.4 归纳证明

1.4.1 整数上的归纳法

1.4.2 更一般形式的整数归纳法

1.4.3 结构归纳法

1.4.4 互归纳法

 1.5 自动机理论的中心概念

1.5.1 字母表

1.5.2 串

1.5.3 语言

1.5.4 问题

 1.6 小结

 1.7 参考文献

第2章 有穷自动机

第3章 正则表达式与正则语言

第4章 正则语言的性质

第5章 上下文无关文法及上下文无关语言

第6章 下推自动机

第7章 上下文无关语言的性质

第8章 图灵机导引

第9章 不可判定性

第10章 难解问题

第11章 其他问题类