形式語言與自動機導論,7/e

彼得·林茨 加利福尼亞大學戴維斯分校計算機科學系榮休教授。他的研究重點是數值分析理論，致力於構建可靠的數值方法並將其用於科學計算中問題求解環境的設計。除本書外，他還著有Exploring Numerical Methods：An Introduction to Scientific Computing。他擁有威斯康星大學博士學位。

譯者序
前言
理論部分
第1章 計算理論概論
1.1 數學預備知識和符號表示
1.1.1 集合
1.1.2 函數和關系
1.1.3 圖和樹
1.1.4 證明方法
1.2 三個基本概念
1.2.1 語言
1.2.2 文法
1.2.3 自動機
1.3 應用*
第2章 有窮自動機
2.1 確定的有窮接受器
2.1.1 確定的接受器和轉移圖
2.1.2 語言和DFA的語言
2.1.3 正則語言
2.2 非確定的有窮接受器
2.2.1 非確定的接受器的定義
2.2.2 為什麽需要非確定性？
2.3 確定與非確定的有窮接受器的等價性
2.4 減少有窮自動機中狀態的化簡*
第3章 正則語言和正則文法
3.1 正則表達式.
3.1.1 正則表達式的形式定義
3.1.2 正則表達式所關聯的語言
3.2 正則表達式和正則語言的聯系
3.2.1 正則表達式表示正則語言
3.2.2 正則語言的正則表達式
3.2.3 描述簡單模式的正則表達式
3.3 正則文法
3.3.1 左線性文法和右線性文法
3.3.2 右線性文法生成正則語言
3.3.3 正則語言的右線性文法
3.3.4 正則語言和正則文法的等價性
第4章 正則語言的性質
4.1 正則語言的封閉性
4.1.1 簡單集合運算的封閉性
4.1.2 其他運算的封閉性
4.2 正則語言的基本問題
4.3 識別非正則語言
4.3.1 鴿巢原理的使用
4.3.2 泵引理
第5章 上下文無關語言
5.1 上下文無關文法
5.1.1 上下文無關文法示例
5.1.2 最左推導和最右推導
5.1.3 推導樹
5.1.4 句型和推導樹的關系
5.2 解析和歧義性
5.2.1 解析和成員資格
5.2.2 文法和語言的歧義性
5.3 上下文無關文法和程序設計語言
第6章 上下文無關文法的化簡和範式
6.1 文法轉換的方法
6.1.1 有用的代入規則
6.1.2 消除無用的產生式
6.1.3 消除λ-產生式
6.1.4 消除單元產生式
6.2 兩種重要的範式
6.2.1 喬姆斯基範式
6.2.2 格雷巴赫範式
6.3 上下文無關文法的成員資格判定算法*
第7章 下推自動機
7.1 非確定的下推自動機
7.1.1 下推自動機的定義
7.1.2 下推自動機接受的語言
7.2 下推自動機和上下文無關語言
7.2.1 上下文無關語言對應的下推自動機
7.2.2 下推自動機對應的上下文無關文法
7.3 確定的下推自動機和確定的上下文無關語言
7.4 確定的上下文無關語言的文法*
第8章 上下文無關語言的性質
8.1 兩個泵引理
8.1.1 上下文無關語言的泵引理
8.1.2 線性語言的泵引理
8.2 上下文無關語言的封閉性和判定算法
8.2.1 上下文無關語言的封閉性
8.2.2 上下文無關語言的一些可判定性質
第9章 圖靈機
9.1 標準的圖靈機
9.1.1 圖靈機的定義
9.1.2 作為語言接受器的圖靈機
9.1.3 作為轉換器的圖靈機
9.2 完成覆雜任務的組合圖靈機
9.3 圖靈論題
第10章 圖靈機的其他模型
10.1 對圖靈機的小改動
10.1.1 自動機類的等價性
10.1.2 可駐停圖靈機
10.1.3 半無窮帶圖靈機
10.1.4 離線圖靈機
10.2 具有更覆雜存儲的圖靈機
10.2.1 多帶圖靈機
10.2.2 多維圖靈機
10.3 非確定的圖靈機
10.4 通用圖靈機
10.5 線性界限自動機
第11章 形式語言和自動機的層次結構
11.1 遞歸語言和遞歸可枚舉語言
11.1.1 非遞歸可枚舉語言
11.1.2 一個非遞歸可枚舉的語言
11.1.3 一個遞歸可枚舉但非遞歸的語言
11.2 無限制文法
11.3 上下文有關文法和語言
11.3.1 上下文有關語言和線性界限自動機
11.3.2 遞歸語言和上下文有關語言的關系
11.4 喬姆斯基層次結構
第12章 算法計算的限制
12.1 圖靈機無法解決的問題
12.1.1 可計算性和可判定性
12.1.2 圖靈機停機問題
12.1.3 不可判定問題的歸約
12.2 遞歸可枚舉語言的不可判定問題
12.3 波斯特對應問題
12.4 上下文無關語言的不可判定問題
12.5 關於效率的問題
第13章 其他計算模型
13.1 遞歸函數
13.1.1 原始遞歸函數
13.1.2 阿克曼函數
13.1.3 μ-遞歸函數
13.2 波斯特系統
13.3 重寫系統
13.3.1 矩陣文法
13.3.2 馬爾可夫算法
13.3.3 L-系統
第14章 計算覆雜性概述
14.1 計算的效率
14.2 圖靈機模型和覆雜性
14.3 語言族和覆雜性類
14.4 覆雜性類P和NP
14.5 幾個NP問題
14.6 多項式