Automata and Computability（自動機與可計算性）

引用

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這樣的複雜性教材。