本书是理论计算机科学方面的经典教材，主要讨论形式语言与自动机理论、可计算性理论和计算复杂性理论等内容。本书强调定义和定理的准确性和严谨性，但在形式化证明中又非常注重符合直觉的理解，避免多余的数学细节。本书分为理论和应用两个部分：理论部分主要介绍有穷自动机、正则语言和文法、上下文无关语言和文法、下推自动机、图灵机、形式语言和自动机的层次结构以及计算复杂性等内容，应用部分主要介绍编译器和解析、LL解析以及LR解析。本书可帮助读者熟悉计算机科学的基础和原理，加强严格的形式化数学证明的能力，适合高等院校计算机科学及相关专业的学生学习，也适合理论计算机科学方向的研究人员参考。

彼得·林茨（Peter Linz）
加利福尼亚大学戴维斯分校计算机科学系荣休教授。他的研究重点是数值分析理论，致力于构建可靠的数值方法并将其用于科学计算中问题求解环境的设计。除本书外，他还著有Exploring Numerical Methods: An Introduction to Scientific Computing。他拥有威斯康星大学博士学位。
苏珊·H. 罗杰（Susan H. Rodger）
杜克大学计算机科学实践教授。她的主要贡献是开发了大量用于理论计算机科学教育的可视化和交互软件，其中，JFLAP软件被世界各地的大学用于形式语言与自动机的实验教学。她曾获得2023年ACM SIGCSE计算机科学教育杰出贡献奖，2019年IEEE计算机协会Taylor L. Booth教育奖，2013年ACM Karl V. Karlstrom杰出教育家奖，2019年杜克大学三一学院David和Janet Vaughn Brooks杰出教学奖。她拥有普渡大学计算机科学博士学位。

目录<br />译者序<br />前言<br />理论部分<br />第 1 章 计算理论概论　　　　　　 2<br />1.1 数学预备知识和符号表示　　　 3<br />1.1.1 集合　　　　　　　　　3<br />1.1.2 函数和关系　　　　　　　5<br />1.1.3 图和树　　　　　　　 8<br />1.1.4 证明方法　　　　　　　 9<br />1.2 三个基本概念　　　　　　　15<br />1.2.1 语言　　　　　　　　　15<br />1.2.2 文法　　　　　　　　 19<br />1.2.3 自动机　　　　　　　 24<br />1.3 应用 *　　　　　　　　 27<br />第 2 章 有穷自动机　　　　　　　 33<br />2.1 确定的有穷接受器　　　　　 33<br />2.1.1 确定的接受器和转移图　　 34<br />2.1.2 语言和 DFA 的语言　　　　36<br />2.1.3 正则语言　　　　　　 40<br />2.2 非确定的有穷接受器　　　　 44<br />2.2.1 非确定的接受器的定义　　 44<br />2.2.2 为什么需要非确定性？　　 48<br />2.3 确定与非确定的有穷接受器的<br />等价性　　　　　　　　 51<br />2.4 减少有穷自动机中状态的<br />化简 *　　　　　　　　 58<br />第 3 章 正则语言和正则文法　　　　 64<br />3.1 正则表达式.　　　　　　　64<br />3.1.1 正则表达式的形式定义　　 64<br />3.1.2 正则表达式所关联的语言　　 65<br />3.2 正则表达式和正则语言的<br />联系　　　　　　　　　　70<br />3.2.1 正则表达式表示正则语言　　 70<br />3.2.2 正则语言的正则表达式　　 72<br />3.2.3 描述简单模式的正则表达式　 77<br />3.3 正则文法　　　　　　　　 80<br />3.3.1 左线性文法和右线性文法　　 80<br />3.3.2 右线性文法生成正则语言　　 81<br />3.3.3 正则语言的右线性文法　　 83<br />3.3.4 正则语言和正则文法的<br />等价性　　　　　　　　 85<br />第 4 章 正则语言的性质　　　　　 89<br />4.1 正则语言的封闭性　　　　　 90<br />4.1.1 简单集合运算的封闭性　　 90<br />4.1.2 其他运算的封闭性　　　　 92<br />4.2 正则语言的基本问题　　　　 99<br />4.3 识别非正则语言　　　　　　102<br />4.3.1 鸽巢原理的使用　　　　　102<br />4.3.2 泵引理　　　　　　 103<br />第 5 章 上下文无关语言　　　　　　113<br />5.1 上下文无关文法　　　　　　114<br />5.1.1 上下文无关文法示例　　　 114<br />5.1.2 最左推导和最右推导　　　 116<br />5.1.3 推导树　　　　　　 117<br />5.1.4 句型和推导树的关系　　　 119<br />5.2 解析和歧义性　　　　　　 123<br />5.2.1 解析和成员资格　　　　　123<br />5.2.2 文法和语言的歧义性　　　 127<br />5.3 上下文无关文法和程序设计<br />语言　　　　　　　　　 132<br />第 6 章 上下文无关文法的化简和<br />范式　　　　　　　　　　135<br />6.1 文法转换的方法　　　　　　136<br />6.1.1 有用的代入规则　　　　　136<br />6.1.2 消除无用的产生式　　　 138<br />6.1.3 消除 λ-产生式　　　　 141<br />6.1.4 消除单元产生式　　　　　143<br />6.2 两种重要的范式　　　　　　149<br />6.2.1 乔姆斯基范式　　　　　150<br />6.2.2 格雷巴赫范式　　　　　152<br />6.3 上下文无关文法的成员资格<br />判定算法 *　　　　　　　 156<br />第 7 章 下推自动机　　　　　　 159<br />7.1 非确定的下推自动机　　　 160<br />7.1.1 下推自动机的定义　　　 160<br />7.1.2 下推自动机接受的语言　　　163<br />7.2 下推自动机和上下文无关<br />语言　　　　　　　　　 168<br />7.2.1 上下文无关语言对应的下推<br />自动机　　　　　　 168<br />7.2.2 下推自动机对应的上<br />下文无关文法　　　　　　173<br />7.3 确定的下推自动机和确定的<br />上下文无关语言　　　　　　179<br />7.4 确定的上下文无关语言的<br />文法 *　　　　　　　　　184<br />第 8 章 上下文无关语言的性质　　　 188<br />8.1 两个泵引理　　　　　　 188<br />8.1.1 上下文无关语言的泵引理　 189<br />8.1.2 线性语言的泵引理　　　 192<br />8.2 上下文无关语言的封闭性<br />和判定算法　　　　　　 196<br />8.2.1 上下文无关语言的封闭性　 197<br />8.2.2 上下文无关语言的一些可判<br />定性质　　　　　　 200<br />第 9 章 图灵机　　　　　　　　　204<br />9.1 标准的图灵机　　　　　　 204<br />9.1.1 图灵机的定义　　　　　205<br />9.1.2 作为语言接受器的图灵机　 209<br />9.1.3 作为转换器的图灵机　　　 212<br />9.2 完成复杂任务的组合图灵机　218<br />9.3 图灵论题　　　　　　　　　222<br />第 10 章 图灵机的其他模型　　　　 225<br />10.1 对图灵机的小改动　　　　 225<br />10.1.1 自动机类的等价性　　　　226<br />10.1.2 可驻停图灵机　　　　226<br />10.1.3 半无穷带图灵机　　　　 228<br />10.1.4 离线图灵机　　　　　　 229<br />10.2 具有更复杂存储的图灵机　　232<br />10.2.1 多带图灵机　　　　　　 232<br />10.2.2 多维图灵机　　　　　　 234<br />10.3 非确定的图灵机　　　　　 236<br />10.4 通用图灵机　　　　　　　238<br />10.5 线性界限自动机　　　　　 242<br />第 11 章 形式语言和自动机的层次<br />结构　　　　　　　　 245<br />11.1 递归语言和递归可枚举<br />语言　　　　　　　　 245<br />11.1.1 非递归可枚举语言　　　　247<br />11.1.2 一个非递归可枚举的语言　 248<br />11.1.3 一个递归可枚举但非递归<br />的语言　　　　　　　 249<br />11.2 无限制文法　　　　　　　251<br />11.3 上下文有关文法和语言　　 256<br />11.3.1 上下文有关语言和线性界<br />限自动机　　　　　　257<br />11.3.2 递归语言和上下文有关语言<br />的关系　　　　　　　 258<br />11.4 乔姆斯基层次结构　　　　 261<br />第 12 章 算法计算的限制　　　　 264<br />12.1 图灵机无法解决的问题　　 264<br />12.1.1 可计算性和可判定性　　 265<br />12.1.2 图灵机停机问题　　　　 265<br />12.1.3 不可判定问题的归约　　 268<br />12.2 递归可枚举语言的不可判定<br />问题　　　　　　　　 271<br />12.3 波斯特对应问题　　　　　 274<br />12.4 上下文无关语言的不可判定<br />问题　　　　　　　　 279<br />12.5 关于效率的问题　　　　　 282<br />第 13 章 其他计算模型　　　　　　　284<br />13.1 递归函数　　　　　　　　285<br />13.1.1 原始递归函数　　　　286<br />13.1.2 阿克曼函数　　　　　　289<br />13.1.3 μ-递归函数　　　　　　290<br />13.2 波斯特系统　　　　　　　292<br />13.3 重写系统　　　　　　　　295<br />13.3.1 矩阵文法　　　　　　296<br />13.3.2 马尔可夫算法　　　　297<br />13.3.3 L-系统　　　　　　　　298<br />第 14 章 计算复杂性概述　　　　 300<br />14.1 计算的效率　　　　　　　300<br />14.2 图灵机模型和复杂性　　　　302<br />14.3 语言族和复杂性类　　　　 305<br />14.4 复杂性类 P 和 NP　　　　 308<br />14.5 几个 NP 问题　　　　　 309<br />14.6 多项式时间归约　　　　　 312<br />14.7 NP 完全性和一个未解决的<br />问题　　　　　　　　 314<br />应用部分<br />第 15 章 编译器和解析　　　　　　　318<br />15.1 编译器　　　　　　　　 318<br />15.2 自顶向下和自底向上的<br />解析　　　　　　　　 326<br />15.3 FIRST 函数　　　　　　 330<br />15.4 FOLLOW 函数　　　　　 337<br />第 16 章 LL 解析　　　　　　　　343<br />16.1 上下文无关文法转换为<br />NPDA　　　　　　　　 344<br />16.1.1 LL 解析的下推自动机　　　 344<br />16.1.2 LL 解析中将上下文无关文<br />法转换为 NPDA 的算法　344<br />16.2 LL(1) 分析表　　　　　 348<br />16.3 LL(1) 解析算法　　　　　 350<br />16.4 LL(k) 解析　　　　　　　353<br />第 17 章 LR 解析　　　　　　　 358<br />17.1 上下文无关文法转换为<br />NPDA　　　　　　　　 359<br />17.2 项和闭包　　　　　　　　364<br />17.3 DFA 建模 LR 解析栈　　　 368<br />17.4 LR(1) 分析表　　　　　 381<br />17.4.1 LR(1) 的解析动作　　　 381<br />17.4.2 LR(1) 分析表算法　　　 381<br />17.5 LR(1) 解析算法　　　　　 388<br />17.6 带有 λ-产生式的 LR(1)<br />解析　　　　　　　　 394<br />17.7 LR(1) 解析冲突　　　　　 404<br />附录 A 有穷状态转换器　　　　　　410<br />附录 B 实用工具 JFLAP　　　　　 425<br />练习题选解　　　　　　　　　　 426<br />参考文献　　　　　　　　　　 478