01 / 导读
导读
引用
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson.
章节概要
第3版约535页，共11章，所以各章篇幅较长：讲这门学科的方法的第一章约36页，讲有限自动机的第二章约48页。本书源自 Hopcroft 和 Ullman 1979年的教材；第2版（2000年）起 Motwani 加入，第3版于2006年出版。Pearson 称这一版经过更新，以简明直接的方式呈现理论概念，并增加了动手的、实用的应用，并且最初附带 Gradiance 这一在线评测工具，Pearson 说它现在已不再随书提供。章节顺序遵循这一学科的惯常路线：先是正则语言，然后是上下文无关语言，最后是图灵机、不可判定性和难解性。
第1章：自动机：方法与疯狂
约36页的导引章节，在定义第一个模型之前先搭起这门学科的框架。
第2章：有限自动机
作为计算的第一个也是最简单的模型的有限自动机，约48页，是开头几章中最长的一章。Google Books 为本书列出的高频词包括非确定性自动机，以及“e-NFA”，即带有空串转移的非确定性扩展形式。
第3章：正则表达式与正则语言
正则表达式及其所描述的语言，从第85页开始。
第4章：正则语言的性质
正则语言的性质，是书中标题含“性质”的两章中的第一章。
第5章：上下文无关文法与语言
文法作为描述语言的第二种方式；推导和语法分析树是书中反复出现的术语。
第6章：下推自动机
与上下文无关文法相对应的机器，其中包括确定性下推自动机（DPDA），它出现在正文的高频词中。
第7章：上下文无关语言的性质
针对上下文无关语言的、与第4章相对应的一章。
第8章：图灵机导论
作为一般计算模型的图灵机，也是后面各章的起点。
第9章：不可判定性
任何算法都无法解决的问题。Google Books 列出的高频词包括修改的波斯特对应问题（MPCP）。
第10–11章：难解问题；其他问题类
原则上可解、但无法高效求解的问题，以及随后讲更多问题类的收尾一章。Google Books 列出的高频词包括多项式时间归约、3SAT、co-NP 和哈密顿回路问题。
核心概念
第1–4章：正则语言
- 有限自动机：第一个计算模型，先于文法和机器来讲。
- 正则表达式：描述同一类语言的记号。
- 正则语言的性质：封闭性与判定问题。
第5–7章：上下文无关语言
- 上下文无关文法与语言。
- 下推自动机：带栈的有限自动机。
- 上下文无关语言的性质。
第8–11章：可计算性与复杂性
- 图灵机：一般的计算模型。
- 不可判定性：任何算法都解决不了的问题。
- 难解问题与其他问题类：高效计算的界限。
评析
优点
- 十一章走完一条完整的路线。 目录从有限自动机经上下文无关语言和图灵机，一直到不可判定性和难解性，所以一本书就覆盖了一门本科课程的全部内容。
- 包含难解性。 第10章和第11章讲难解问题和更多的问题类，而 Kozen 的章节列表止于可计算性。
- 提法力求易懂。 Pearson 强调简明直接的呈现和实用的应用。
- 长期积累。 1979年到2006年间的三个版本，始终由 Hopcroft 和 Ullman 担任作者，使它成为这一领域有影响的教材。
局限
- 高深的理论比旧版少。 关于本书历史的记述指出，从第2版开始，应用部分得到扩充，一些较高深的理论被删去。需要1979年版更深内容的课程，要另配教材。
- 章节较长。 开头几章有36到48页，与由许多短章组成的教材相比，模块性较弱。
- 随书的在线工具已不存在。 第3版附带的 Gradiance 已不再受 Pearson 支持，围绕它搭建的作业系统无法使用。
在课程中的定位
这是关于形式语言、自动机和可计算性的、篇幅较大的经典教材，最直接的比较对象是 Sipser 的 Introduction to the Theory of Computation，后者同样是清晰的高年级入门书，涵盖自动机、形式语言、可计算性和复杂性。两本都可以作主教材。Kozen 的 Automata and Computability 是由短章组成的更紧凑的替代选择，讲到了 Kleene 代数、哥德尔定理等话题，但止于复杂性之前。
Linz 和 Rodger 的 An Introduction to Formal Languages and Automata 把讲解和例子置于形式化之前，适合想要更多解释的学生作为配套。MacCormick 的 What Can Be Computed? 通过 Python 程序来讲同样的理论，Arora 和 Barak 的 Computational Complexity 则是第10章、第11章之后的研究生层次的延伸。
如何使用本书
Pearson 的页面没有说明先修要求；集合、关系、归纳法和证明是合理的背景，编程经验有助于理解书中的实用动机。
一个实用的读法：
- 核心： 第1–4章讲正则语言，第5–6章讲上下文无关文法和下推自动机，第8–9章讲图灵机和不可判定性。
- 初读从简： 第4章和第7章这两个“性质”章节，初读时可以读得轻一些，等熟悉证明技巧后再回来。
- 选读： 如果课程包括复杂性，就读第10章和第11章，否则另用复杂性教材。
认真做习题，并且对每一种模型（有限自动机、文法、下推自动机、图灵机），手写一个小例子，再把它转换成书中接下来讲的等价模型。