An Introduction to Formal Languages and Automata（形式語言與自動機導論）

引用

Linz, P., & Rodger, S. H. (2023). An Introduction to Formal Languages and Automata (7th ed.). Jones & Bartlett Learning.

章節概要

第七版分兩部共十七章。第一部「Theory」即第六版的十四章，並補充了新習題；第二部「Applications」為新增，把前面的理論應用到編譯器中的語法剖析。其後是兩個附錄、部分習題的解答與提示，以及延伸閱讀文獻，全書約570頁。標有星號的小節可以省略，不影響後續內容。每章末尾在原有習題之外，新增了一組較簡單的「Introductory Exercises（入門習題）」。

第1章：Introduction to the Theory of Computation（計算理論導論）

複習數學預備知識（集合、函數與關係、圖與樹、證明技巧），接著介紹本書的三個基本概念：語言、文法與自動機。一個選讀小節概述若干應用。

第2章：Finite Automata（有限自動機）

以轉移圖定義確定性有限接受器，並用它定義正規語言；接著介紹非確定性接受器，說明非確定性為何有用，並證明兩者等價。一個選讀小節討論如何減少狀態數。

第3章：Regular Languages and Regular Grammars（正規語言與正規文法）

介紹正規表示式，證明它恰好描述正規語言，並說明它在描述簡單樣式上的用法。右線性文法與左線性文法被證明會產生同一個語言族。

第4章：Properties of Regular Languages（正規語言的性質）

討論在集合運算及其他運算下的封閉性、基本的判定問題，以及如何利用鴿籠原理與抽取引理證明某個語言不是正規語言。

第5章：Context-Free Languages（上下文無關語言）

介紹上下文無關文法、最左推導與最右推導以及推導樹，接著討論剖析、成員判定與歧義性，最後說明上下文無關文法在程式語言中的角色。

第6章：Simplification of Context-Free Grammars and Normal Forms（上下文無關文法的化簡與正規形式）

說明如何移除無用產生式、λ產生式與單元產生式，並介紹喬姆斯基正規形式與格瑞巴赫正規形式。一個選讀小節提供上下文無關文法的成員判定演算法。

第7章：Pushdown Automata（下推自動機）

定義非確定性下推自動機，並從兩個方向證明它與上下文無關文法等價；接著討論確定性下推自動機與確定性上下文無關語言，另有一個選讀小節談它們的文法。

第8章：Properties of Context-Free Languages（上下文無關語言的性質）

提出上下文無關語言與線性語言的抽取引理、封閉性質，以及上下文無關語言的若干可判定性質。

第9章：Turing Machines（圖靈機）

把標準圖靈機分別定義為語言接受器與轉換器，說明如何組合多部圖靈機完成複雜工作，並陳述圖靈論題。

第10章：Other Models of Turing Machines（圖靈機的其他模型）

檢視各種變形（具停留選項、半無限磁帶、離線圖靈機）、具有更複雜儲存的圖靈機（多磁帶與多維）、非確定性圖靈機、通用圖靈機與線性有界自動機，並確認哪些變形不會增加計算能力。

第11章：A Hierarchy of Formal Languages and Automata（形式語言與自動機的階層）

區分遞迴語言與遞迴可列舉語言，並舉出不屬於各自類別的語言；接著介紹無限制文法與上下文相關文法，建立喬姆斯基階層。

第12章：Limits of Algorithmic Computation（演算法計算的極限）

討論可計算性與可判定性、停機問題、把一個不可判定問題歸約到另一個問題、關於遞迴可列舉語言與上下文無關語言的不可判定問題，以及波斯特對應問題，最後簡短談到效率問題。

第13章：Other Models of Computation（其他計算模型）

介紹其他計算模型：原始遞迴函數與μ遞迴函數（含阿克曼函數）、波斯特系統，以及矩陣文法、馬可夫演算法與L系統等改寫系統。

第14章：An Overview of Computational Complexity（計算複雜度概觀）

把圖靈機模型與複雜度連結起來，介紹語言族與複雜度類別，討論P與NP、若干NP問題的例子、多項式時間歸約與NP完全性，最後停在P是否等於NP這個尚未解決的問題。

第15–17章：Compilers and Parsing（編譯器與語法剖析）；LL Parsing（LL剖析）；LR Parsing（LR剖析）

第二部從編譯器的工作、由上而下與由下而上的剖析，以及FIRST與FOLLOW函數談起。第16章為LL剖析把上下文無關文法轉換為非確定性下推自動機，建構LL(1)剖析表與剖析演算法，並有一節討論LL(k)。第17章對LR剖析做同樣的工作：項目與閉包、模擬剖析堆疊的DFA、LR(1)剖析表與演算法、λ產生式，以及剖析衝突。

附錄

附錄A討論有限狀態轉換器（米利機與摩爾機、兩者的等價性、最小化及其限制）。附錄B介紹JFLAP，一套用來建構與測試自動機和文法的免費互動式工具。

核心概念

第1–4章：基礎與正規語言

• 語言、文法、自動機：本書的三個基本概念，在第1章一併介紹。
• 非確定性：允許多種可能的移動；對有限接受器來說，它帶來便利，但不增加能力。
• 正規表示式：恰好描述有限自動機所接受之語言的一種記法。
• 抽取引理：所有正規語言都具有的性質，用來證明某個語言不是正規語言。

第5–8章：上下文無關語言

• 推導樹與歧義性：推導的結構，以及允許一個字串有多棵推導樹的文法。
• 喬姆斯基與格瑞巴赫正規形式：任何上下文無關語言都能採用的受限文法形式。
• 下推自動機：附有堆疊的有限自動機，其非確定性版本與上下文無關文法等價。

第9–13章：圖靈機與可計算性

• 圖靈論題：任何機械式計算都能由圖靈機完成的主張。
• 通用圖靈機：能依據任何其他圖靈機的描述來模擬它的圖靈機。
• 喬姆斯基階層：正規、上下文無關、上下文相關與遞迴可列舉這幾個層層包含的語言族。
• 停機問題與歸約：最基本的不可判定問題，以及證明其他問題不可判定的方法。

第14章：複雜度

• P與NP：可在確定性與非確定性多項式時間內解決的問題。
• NP完全性：在多項式時間歸約之下，NP中最困難的問題。

第15–17章：語法剖析

• FIRST與FOLLOW：定義在文法符號上、用來建構剖析表的函數。
• LL(1)與LR(1)剖析：向前看一個符號、以剖析表驅動的由上而下與由下而上剖析，由下推自動機推導而來。

評析

優點

• 直覺與例子優先。 序言表示本書重視直觀的動機與以例子說明概念，寧可選擇容易掌握的論證，而非簡潔卻難懂的論證，並以一個具動機作用的例子引出每個核心概念。
• 在解題中學習。 每節末的習題從順著正文再往前一兩步的簡單題，到極困難的題目都有；第七版另在章末加入入門習題，作為通往較難習題的橋梁。書中附有部分習題的解答與提示。
• 直接回應「這有什麼用」。 第二部把下推自動機與文法應用到LL與LR剖析；作者表示，這是為了回應學生對理論實際用途的疑問。
• 工具支援。 附錄B介紹免費互動式工具JFLAP，序言強力推薦用它來理解概念，並節省建構習題解答的時間。

局限

• 證明較為簡略。 序言坦承許多證明只交代動機，省略例行細節；想要完整形式化證明的讀者，需要參考更嚴謹的教科書，或自行補齊步驟。
• 複雜度只作概觀。 計算複雜度只占一章，止於NP完全性；空間複雜度與更深入的主題都沒有處理。
• 一學期放不下。 序言指出，要在一學期內教完第一部的大部分內容就必須有所取捨；若還要教第二部，就得把第一部後段的一些小節講得輕一些。

在課程中的定位

在計算理論這門課的書單中，本書是一本平易近人的入門教科書，依標準順序從有限自動機講到NP完全性。另一個入門選擇是 MacCormick 的 What Can Be Computed?：它透過Python程式來談可計算性與複雜度，有限自動機只占一章，也沒有專講文法或下推自動機的章節。若課程在形式語言上花較多時間，Linz 與 Rodger 較為合適；兩本書也能彼此互補。

Kozen 的 Automata and Computability（由附完整證明的短篇講次組成）、Hopcroft、Motwani 與 Ullman 的 Introduction to Automata Theory, Languages, and Computation 以及 Sipser 的 Introduction to the Theory of Computation 涵蓋相近的範圍，證明更為形式化；覺得 Linz 的證明概要太過簡略的學生，可以閱讀這些書中相對應的小節。Arora 與 Barak 的 Computational Complexity 是研究所教科書，對複雜度的討論遠遠超出第14章的概觀。

如何使用本書

序言設定的讀者是資訊科學與電腦工程系的二、三年級學生。先備條件包括：熟悉一種高階程式語言、具備資料結構與演算法的基礎，以及一門不可或缺的離散數學課程，內容涵蓋集合、函數、關係、邏輯與數學推理。

• 核心（第一部）： 依序讀第1–12章；序言提醒，除了標星號的小節（例如1.3、2.4、6.3、7.4）之外，幾乎沒有什麼可以跳過而不造成後面的困難。
• 可以從簡： 序言指出，第一部後段的許多小節可以從簡處理或略過而不影響連貫，藉此為第二部騰出約一週；討論其他計算模型的第13章是合適的候選。
• 複雜度： 第14章初步介紹P、NP與NP完全性。
• 應用（第二部）： 第15–17章適合準備修編譯器課程的學生，課堂時間不夠時也可作為有引導的課外閱讀。

先做入門習題，確認自己理解每個定義，再進入正式習題。把例子中的每個自動機與文法都在JFLAP中建出來，用字串測試之後再動筆寫證明。書中只給出證明概要的地方，自己把缺少的細節寫出來；這正是序言所建議的練習方式。