Introduction to Automata Theory, Languages, and Computation, 2/e(精裝本)
暫譯: 自動機理論、語言與計算導論（第二版，精裝本）

描述

自從這本關於形式語言、自動機理論和計算複雜度的經典書籍首次出版以來，已經過了20多年。隨著這次期待已久的修訂，作者繼續以簡潔明瞭的方式呈現理論，並著眼於實際應用。他們對這本書進行了修訂，使其對當今的學生更具可讀性，包括增加了更多有關證明寫作的材料、更多的圖形和圖片以傳達思想、側邊框以突出其他有趣的材料，以及較不正式的寫作風格。每章結尾的練習題，包括一些新的、更簡單的練習，幫助讀者確認和增強對材料的理解。

適合的課程

計算理論/計算機科學理論，自動機理論。

特點

- 新！完全重寫以減少正式性，使當今的學生更易於接觸。
- 新！增加了圖形和圖片的使用，以幫助傳達思想。
- 新！對定義和證明提供了更多的細節和直觀理解。
- 新！提供特殊的側邊框以呈現可能引起讀者興趣的補充材料。
- 新！包含更多的練習題，包括許多較低難度的題目。
- 新！為PDA和圖靈機提供類似程式的符號表示。
- 新！增加了可在線獲得的解題數量和新的程式設計練習。

目錄

（注意：每章結尾都有摘要和參考文獻。）

1. 自動機：方法與瘋狂。
- 為什麼學習自動機理論？
- 有限自動機介紹。
- 結構表示。
- 自動機與複雜度。
- 正式證明介紹。
- 演繹證明。
- 簡化為定義。
- 其他定理形式。
- 看似不是如果-那麼語句的定理。
- 其他證明形式。
- 證明集合的等價性。
- 反證法。
- 反例。
- 歸納證明。
- 整數的歸納。
- 更一般的整數歸納形式。
- 結構歸納。
- 互相歸納。
- 自動機理論的核心概念。
- 字母表。
- 字串。
- 語言。
- 問題。

2. 有限自動機。
- 有限自動機的非正式圖像。
- 基本規則。
- 協議。
- 使自動機忽略行動。
- 整個系統作為一個自動機。
- 使用產品自動機來驗證協議。
- 確定性有限自動機。
- 確定性有限自動機的定義。
- DFA如何處理字串。
- DFA的簡化符號。
- 將轉移函數擴展到字串。
- DFA的語言。
- 第2.2節的練習題。
- 非確定性有限自動機。
- 非確定性有限自動機的非正式觀點。
- 非確定性有限自動機的定義。
- 擴展轉移函數。
- NFA的語言。
- 確定性與非確定性有限自動機的等價性。
- 子集構造的壞情況。
- 第2.3節的練習題。
- 應用：文本搜索。
- 在文本中查找字串。
- 用於文本搜索的非確定性有限自動機。
- 用於識別關鍵字集的DFA。
- 第2.4節的練習題。
- 帶有ε轉移的有限自動機。
- ε轉移的用途。
- e-NFA的正式符號。
- ε閉包。
- e-NFA的擴展轉移和語言。
- 消除ε轉移。

3. 正規表達式和語言。
- 正規表達式。
- 正規表達式的運算子。
- 構建正規表達式。
- 正規表達式運算子的優先順序。
- 有限自動機與正規表達式。
- 從DFA到正規表達式。
- 通過消除狀態將DFA轉換為正規表達式。
- 將正規表達式轉換為自動機。
- 第3.2節的練習題。
- 正規表達式的應用。
- UNIX中的正規表達式。
- 詞法分析。
- 在文本中查找模式。
- 第3.3節的練習題。
- 正規表達式的代數法則。
- 結合性和交換性。
- 同一性和消去元。
- 分配法則。
- 幂等法則。
- 涉及閉包的法則。
- 發現正規表達式的法則。
- 測試正規表達式代數法則。
- 第3.4節的練習題。

4. 正規語言的性質。
- 證明語言不是正規的。
- 正規語言的抽水引理。
- 抽水引理的應用。
- 第4.1節的練習題。
- 正規語言的閉合性質。
- 正規語言在布林運算下的閉合。
- 反轉。
- 同態。
- 反同態。
- 第4.2節的練習題。
- 正規語言的決策性質。
- 轉換表示法。
- 測試正規語言的空性。
- 測試正規語言的成員資格。
- 第4.3節的練習題。
- 自動機的等價性和最小化。
- 測試狀態的等價性。
- 測試正規語言的等價性。
- DFA的最小化。
- 為什麼最小化的DFA無法被超越。
- 第4.4節的練習題。

5. 上下文無關文法和語言。
- 上下文無關文法。
- 一個非正式的例子。
- 上下文無關文法的定義。
- 使用文法的推導。
- 最左推導和最右推導。
- 文法的語言。
- 句子形式。
- 第5.1節的練習題。
- 解析樹。
- 構建解析樹。