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章，否則另用複雜性教材。
認真做習題，並且對每一種模型（有限自動機、文法、下推自動機、圖靈機），手寫一個小例子，再把它轉換成書中接下來講的等價模型。