01 / 导读
导读
引用
Kozen, D. C. (1997). Automata and Computability. Springer.
章节概要
本书由五十个短章组成，每章三到十页，在400页的全书中占据第3页到第298页。Springer 把它描述为面向本科生、介绍可计算性基本理论模型的书，分三个部分：先是有限自动机，然后是下推自动机和上下文无关语言，最后是图灵机，以有效可计算性、可判定性和哥德尔不完全性定理结束。出版社还说，若干补充章节介绍更进一步的概念，并提供了从易到难的大量习题。Springer 的章节列表没有标明哪些是补充章节。
第1–6章：课程路线图与历史视角；字符串与集合；有限自动机与正则集；再谈正则集；非确定性有限自动机；子集构造
开篇是带有历史视角的路线图，随后是一章讲字符串与集合的记号，以及四章讲确定性与非确定性有限自动机，以子集构造收尾。
第7–10章：模式匹配；模式匹配与正则表达式；正则表达式与有限自动机；Kleene代数与正则表达式
从模式匹配进入正则表达式，讲它与有限自动机的等价性，再到代数化的处理——Kleene代数。
第11–13章：同态；有限自动机的局限；运用泵引理
先讲对同态的封闭性，再讲有限自动机做不到什么，以及泵引理如何应用。
第14–17章：DFA状态最小化；最小化算法；Myhill–Nerode关系；Myhill–Nerode定理
确定性自动机的最小化，先作为概念，再作为算法，随后是Myhill–Nerode关系及其定理。
第18–22章：压缩非确定性自动机；项上的自动机；项自动机的Myhill–Nerode定理；双向有限自动机；2DFA与正则集
正则语言理论的扩展：压缩非确定性自动机，有自己的Myhill–Nerode定理的项上自动机，以及双向自动机。
第23–26章：上下文无关文法与语言；括号匹配；范式；上下文无关语言的泵引理
上下文无关部分从文法开始，接着是一章讲括号匹配，然后是范式，以及上下文无关语言的泵引理。
第27–31章：下推自动机；接受状态与空栈；PDA与CFG；用CFG模拟NPDA；确定性下推自动机
下推自动机、两种接受条件、与上下文无关文法的等价性，以及确定性下推自动机。
第32–35章：语法分析；Cocke–Kasami–Younger算法；Chomsky–Schützenberger定理；Parikh定理
关于上下文无关语言的算法和结构性定理：语法分析、CKY算法、Chomsky–Schützenberger定理和Parikh定理。
第36–40章：图灵机与有效可计算性；再谈图灵机；等价模型；通用机与对角化；可判定与不可判定的问题
图灵机作为有效可计算性的模型，等价模型，通用机与对角化，以及最初的可判定和不可判定问题。
第41–43章：归约；Rice定理；关于CFL的不可判定问题
以归约作为证明不可判定性的工具，然后是Rice定理，再是关于上下文无关语言的不可判定问题。
第44–46章：其他形式系统；λ演算；While程序
计算的其他形式系统：λ演算和while程序。
第47–50章：超越不可判定性；哥德尔不完全性定理；不完全性定理的证明；哥德尔的证明
全书最后讲不可判定性之外的内容，以及三章关于哥德尔不完全性定理及其证明。
核心概念
第1–22章：正则语言
- 非确定性与子集构造：如何把非确定性自动机转换为确定性自动机。
- 正则表达式与Kleene代数：正则集的等价描述。
- 泵引理与Myhill–Nerode定理：证明语言是否正则的工具。
- DFA最小化：求出最小的确定性自动机。
第23–35章：上下文无关语言
- 上下文无关文法、范式和上下文无关语言的泵引理。
- 下推自动机，非确定性的和确定性的。
- 语法分析与Cocke–Kasami–Younger算法。
第36–50章：可计算性
- 图灵机、通用机与对角化。
- 归约与Rice定理：证明不可判定性的方法。
- λ演算与while程序：可计算性的其他形式系统。
- 哥德尔不完全性定理。
评析
优点
- 章节短小。 五十章，每章三到十页，都可以一次读完，便于布置作业，也便于逐章自学。
- 节奏适中的第一门课。 出版社把本书定位为面向有一些初等离散数学基础的学生的、节奏适中的第一门课，并提供了从易到难的大量习题。
- 超出通常核心的广度。 除了正则语言、上下文无关语言和图灵机，章节列表里还有Kleene代数、项自动机、双向自动机、Parikh定理、λ演算、while程序和哥德尔定理，为学有余力的学生提供了选择。
- 完整的脉络。 从有限自动机经下推自动机到图灵机和不完全性定理，这条线索从章节顺序上就能看出来。
局限
- 没有计算复杂性理论。 章节列表中没有时间或空间复杂度、NP完全性的章节；全书止于可计算性。需要复杂性内容的课程要另配教材。
- 补充章节没有标出。 出版社说有些章节是补充性的，但章节列表没有区分，所以读者要自己选择阅读路径。
- 偏重理论。 标题中带有应用色彩的只有模式匹配和语法分析，想看应用的读者在本书里找到的不多。
在课程中的定位
Kozen 的书是计算理论的一门紧凑的入门课。在本课程的书中，Sipser 的 Introduction to the Theory of Computation 是延伸到复杂性的清晰的高年级入门书，是补上 Kozen 所略去部分的自然搭配。Hopcroft、Motwani 和 Ullman 的 Introduction to Automata Theory, Languages, and Computation 是更大部头的经典教材，确实讲到了难解性。Linz 和 Rodger 的 An Introduction to Formal Languages and Automata 重视讲解和例子，适合希望得到比 Kozen 更多解释的读者。MacCormick 的 What Can Be Computed? 把理论建立在 Python 程序之上，适合喜欢从代码入手的读者。
Arora 和 Barak 的 Computational Complexity 是侧重复杂性的研究生教材，是读完 Kozen 的可计算性内容之后自然的延伸。
如何使用本书
Springer 说，有一些初等离散数学经验的学生会发现本书是节奏适中的第一门课。因此，熟悉集合、关系和归纳证明是合理的先修要求。
一个实用的读法：
- 核心路径： 第1–6章和第9章讲有限自动机与正则表达式；第12–13章讲泵引理；第23章、第25章和第27–29章讲上下文无关语言与下推自动机；第36–42章讲图灵机、归约和Rice定理。
- 选读： Kleene代数（第10章）、DFA最小化与Myhill–Nerode（第14–17章）、语法分析（第32–33章），以及讲其他形式系统和哥德尔的最后几章（第44–50章），视兴趣而定。
- 进阶： 项自动机、双向自动机、Chomsky–Schützenberger定理与Parikh定理。
边读边做习题；出版社强调习题丰富，从易到难都有。如果课程继续讲到NP完全性，要配上Sipser这样的复杂性教材。