书 · 1979 · 约翰·E. 霍普克罗夫特（John E. Hopcroft）、杰弗里·D. 乌尔曼（Jeffrey D. Ullman）

《自动机理论、语言和计算导论》

计算机与 AI书单第 37 名

一句话结论

这本书教你分清三个问题：一种机器能表达什么、一个问题能否由算法解决，以及解决它需要多少时间和空间。

值不值得读完整本？

值得完整读，尤其适合想打牢计算机科学理论基础的人；但应分两轮读，并配合证明与构造练习。

先读第一章所需的数学基础，再连读第二至八章，掌握有限自动机、上下文无关文法、下推自动机、图灵机和不可判定性。
接着读第九章建立语言层级地图，再读第十二、十三章，把“能不能算”推进到“需要多少资源”。这部分不能因为不直接涉及编程而跳过。
第二轮细读第十、十一章，理解确定性上下文无关语言与封闭性质。第十二章较抽象的复杂性结果和第十四章的其他语言类可以先浏览，待主线清楚后返回。
每种模型至少亲手构造一个例子、完成一次表示转换、解释一个能力限制。只记名称和包含关系，难以真正读懂。
把书中的开放问题标记为“1979年的研究状态”；部分问题后来已有答案，宜配合后续论文阅读。

核心观点

1. 不同表示可以拥有相同的计算能力

确定性有限自动机、非确定性有限自动机和正则表达式描述的是同一类语言。表达形式不同，不等于能处理的问题范围不同。

为什么：非确定性有限自动机允许同一输入对应多条计算路径，但这些路径当前可能处于哪些状态，可以整体记成一个状态集合。原机器的状态数量有限，因此可能的状态集合也有限，确定性机器就能逐步更新这个集合。正则表达式中的选择、连接和重复，也能通过组合自动机实现；反过来，自动机的接受路径可以转写成表达式。这些双向构造证明了表达能力相同，但没有保证表示大小或运行代价相同。

2. 证明能力边界，要找所有机器都绕不过的结构

要证明某类机器做不到一件事，不能只展示几次设计失败。抽引引理、封闭性质和状态可区分性，提供了适用于整个模型类别的论证工具。

为什么：有限自动机处理足够长的输入时必然重复访问某个状态，因此接受路径中会出现可以重复经过的环。这个事实使每个正则语言都必须满足一定的抽引条件；若一个语言无法满足，就能排除所有有限自动机。封闭性质则让我们通过取交集、取补等操作，把待研究语言与已经了解的语言联系起来。状态可区分性的思路进一步指出：如果两个输入前缀能被某个后缀区分，机器就不能把它们记成同一个状态。这些方法解释了限制来自哪里，而不只是宣布一个语言“不正则”。

3. 栈把递归变成可执行过程，但非确定性不能随便消去

上下文无关文法用递归规则生成语言，下推自动机用栈识别同一类语言。这里必须保留“非确定性”这个条件，确定性下推自动机的表达能力更弱。

为什么：递归结构会留下尚未完成的任务，而栈按后进先出的次序保存这些任务，正好适合处理嵌套关系。模拟文法推导时，机器可以把待展开的符号放在栈中，再根据产生式逐步替换、匹配输入。反过来，下推自动机的一段入栈和出栈过程也能用文法规则描述。可是，选择哪条产生式、什么时候从记录转入匹配，未必能由眼前的信息唯一决定。因此，有限自动机中确定性与非确定性等价的结论，不能直接搬到下推自动机上。

4. 能识别不等于能判定，通用计算也有极限

识别一个语言，只要求对属于它的输入最终接受；判定还要求对所有输入都停机并回答是或否。图灵机能够模拟一般算法，却仍存在它无法判定的问题。

为什么：对不属于语言的输入，识别程序可能一直运行，所以“等得更久”不能自动变成否定答案。通用图灵机能够读取其他机器的编码并模拟其行为，使程序本身也成为可处理的数据。于是可以构造自指问题：假设存在一个总能正确回答某类机器行为的判定程序，再据此构造与其回答相反的机器，就会产生矛盾。这证明缺少通用判定算法是模型中的原则性限制，而不只是程序员暂时没有找到办法。

5. 归约把一个问题的困难传给另一个问题

归约把问题甲的实例转换成问题乙的实例，并保留答案，使乙的解法能够用于解决甲。它让不同表面的困难得到统一比较。

为什么：如果已知甲不可判定，又能把甲可计算地转换成乙，那么乙的通用判定算法就会反过来给出甲的判定算法，造成矛盾。因此，证明乙困难时，要把已知困难的问题送进乙，而不是只证明乙能被送进一个困难问题。讨论效率时，还必须限制转换本身的资源开销，否则转换过程可能已经完成了全部困难工作。本书讨论多项式时间归约和对数空间归约，并在介绍非确定性多项式时间完全性时采用对数空间归约的约定。

6. 能算还不够，还要看时间、空间与难度层级

可判定的问题仍可能需要极大的计算资源，复杂性理论因此按输入长度衡量时间和空间。完全问题则把一个复杂性类中最困难的问题联系起来。

为什么：计算资源随输入长度增长的速度，比某台机器处理一个小例子的快慢更能揭示算法的扩展能力。确定性多项式时间与非确定性多项式时间的区别，使“迅速找到答案”和“给出候选答案后迅速核查”成为需要分开的能力。若一个问题属于后一类，而且该类的所有问题都能按规定归约到它，那么它就是相应的完全问题；它一旦有确定性多项式时间算法，整类问题都会获得这种算法。这个结论把许多困难联系起来，却没有单独证明这些问题必然不存在快速算法。书中还研究空间复杂性和资源层级，说明复杂性的地图远不止这一组问题。

反对意见

作为自然语言理论教材，覆盖面有限（Hans-Jörg Tiede）

Tiede在《The Mathematics of Language》书评中，将该书与霍普克罗夫特、乌尔曼的教材作比较，指出后者没有着重处理一些对自然语言研究尤其重要的形式语言问题。这个批评针对选题范围：学会语言识别与机器等价，并不意味着已经掌握语言学所需的全部形式工具。它没有否定本书的数学结果。

一次性输入输出不足以描述持续交互（Peter Wegner、Dina Goldin）

Wegner和Goldin在《Interaction, Computability, and Church’s Thesis》中主张，对象系统和分布式系统会持续接受环境输入，其行为不能充分用一次性输入、计算、输出的任务来描述。他们要求扩展研究对象，把交互历史与环境作用纳入模型。这是对计算建模范围的挑战，并非本书的直接书评，也不能据此说图灵机框架内的不可判定性定理失效。

处理真实语言还需要数据与统计（Alon Halevy、Peter Norvig、Fernando Pereira）

三人在《The Unreasonable Effectiveness of Data》中强调，自然语言包含大量例外和细微差别，大规模数据能够支持难以靠简洁规则充分刻画的任务。对照本书，这提示我们：精确描述哪些串被接受，与从真实语料中学习有用行为，是不同的研究目标。这是导读提供的对照视角；该论文没有直接批评这部教材。