自動機理論、語言和計算導論（原書第3版·典藏版）

譯者序
前言
第1章 自動機：方法與體驗 1
1.1 為什麼研究自動機理論 1
1.1.1 有窮自動機簡介 1
1.1.2 結構標記法 3
1.1.3 自動機與複雜性 3
1.2 形式化證明簡介 3
1.2.1 演繹證明 4
.2 求助於定義 6
1.2.3 其他定理形式 7
1.2.4 表面上不是“如果-則”命題的定理 9
1.3 其他的證明形式 9
1.3.1 證明集合等價性 9
1.3.2 逆否命題 10
1.3.3 反證法 12
1.3.4 反例 12
1.4 歸納證明 13
1.4.1 整數上的歸納法 13
1.4.2 一般形式的整數歸納法 16
1.4.3 結構歸納法 16
1.4.4 互歸納法 18
1.5 自動機理論的中心概念 19
1.5.1 字母表 19
1.5.2 串 20
1.5.3 語言 21
1.5.4 問題 21
1.6 小結 23
1.7 參考文獻 24
 
第2章 有窮自動機 25
2.1 有窮自動機的非形式化描述 25
2.1.1 基本規則 26
2.1.2 協議 26
2.1.3 允許自動機忽略動作 27
2.1.4 整個系統成為一個自動機 29
2.1.5 用乘積自動機驗證協議 30
2.2 確定型有窮自動機 30
2.2.1 確定型有窮自動機的定義 31
2.2.2 DFA如何處理串 31
2.2.3 DFA的簡化記號 32
2.2.4 把轉移函數擴展到串 33
2.2.5 DFA的語言 35
2.2.6 習題 35
2.3 非確定型有窮自動機 37
2.3.1 非確定型有窮自動機的非形式化觀點 37
2.3.2 非確定型有窮自動機的定義 38
2.3.3 擴展轉移函數 39
2.3.4 NFA的語言 39
2.3.5 確定型有窮自動機與非確定型有窮自動機的等價性 40
2.3.6 子集構造的壞情形 43
2.3.7 習題 45
2.4 應用：文本搜索 46
2.4.1 在文本中查找串 46
2.4.2 文本搜索的非確定型有窮自動機 46
2.4.3 識別關鍵字集合的DFA 47
2.4.4 習題 49
2.5 帶e 轉移的有窮自動機 49
2.5.1 e 轉移的用途 49
2.5.2 e-NFA的形式化定義 50
2.5.3 e 閉包 51
2.5.4 e-NFA的擴展轉移和語言 52
2.5.5 消除 e 轉移 53
2.5.6 習題 54
2.6 小結 55
2.7 參考文獻 55
 
第3章 規則運算式與正則語言 57
3.1 規則運算式 57
3.1.1 規則運算式運算子 57
3.1.2 構造規則運算式 59
3.1.3 規則運算式運算子的優先順序 60
3.1.4 習題 61
3.2 有窮自動機和規則運算式 61
3.2.1 從DFA到規則運算式 62
3.2.2 通過消除狀態把DFA轉化為規則運算式 65
.2.3 把規則運算式轉化為自動機 69
3.2.4 習題 72
3.3 規則運算式的應用 73
3.3.1 UNIX中的規則運算式 73
3.3.2 詞法分析 74
3.3.3 查找文本中的模式 76
3.3.4 習題 77
3.4 規則運算式代數定律 77
3.4.1 結合律與交換律 78
3.4.2 單位元與零元 78
3.4.3 分配律 79
3.4.4 冪等律 79
3.4.5 與閉包有關的定律 79
3.4.6 發現規則運算式定律 80
3.4.7 檢驗規則運算式代數定律 81
3.4.8 習題 82
3.5 小結 83
3.6 參考文獻 84
 
第4章 正則語言的性質 85
4.1 證明語言的非正則性 85
4.1.1 正則語言的泵引理 85
4.1.2 泵引理的應用 87
4.1.3 習題 88
4.2 正則語言的封閉性 89
4.2.1 正則語言在布耳運算下的封閉性 89
4.2.2 反轉 93
4.2.3 同態 94
4.2.4 逆同態 96
4.2.5 習題 99
4.3 正則語言的判定性質 102
4.3.1 在各種表示之間轉化 102
4.3.2 測試正則語言的空性 104
4.3.3 測試正則語言的成員性 104
4.3.4 習題 105
4.4 自動機的等價性和 小化 105
4.4.1 測試狀態的等價性 105
4.4.2 測試正則語言的等價性 107
4.4.3 DFA 小化 108
4.4.4 為什麼不能比 小DFA 小 110
4.4.5 習題 111
4.5 小結 112
4.6 參考文獻 112
 
第5章 上下文無關文法及上下文無關語言 115
5.1 上下文無關文法 115
5.1.1 一個非形式化的例子 115
5.1.2 上下文無關文法的定義 116
5.1.3 使用文法來推導 118
5.1.4 左推導和 右推導 119
5.1.5 文法的語言 120
5.1.6 句型 121
5.1.7 習題 122
5.2 語法分析樹 124
5.2.1 構造語法分析樹 124
5.2.2 語法分析樹的產生 125
5.2.3 推理、推導和語法分析樹 125
5.2.4 從推理到樹 126
5.2.5 從樹到推導 127
5.2.6 從推導到遞迴推理 129&
5.2.7 習題 131
5.3 上下文無關文法的應用 131
5.3.1 語法分析器 131
5.3.2 語法分析器生成器YACC 133
5.3.3 標記語言 134
5.3.4 XML和文檔類型定義 135
5.3.5 習題 140
5.4 文法和語言的歧義性 141
5.4.1 歧義文法 141
5.4.2 去除文法的歧義性 143
.4.3 左推導作為表達歧義性的一種方式 145
5.4.4 固有的歧義性 146
5.4.5 習題 147
5.5 小結 148
5.6 參考文獻 148
 
第6章 下推自動機 151
6.1 下推自動機的定義 151
6.1.1 非形式化的介紹 151
6.1.2 下推自動機的形式化定義 152
6.1.3 PDA的圖形表示 154
6.1.4 PDA的暫態描述 154
6.1.5 習題 157
6.2 PDA的語言 158
6.2.1 以終結狀態方式接受 158
6.2.2 以空棧方式接受 159
6.2.3 從空棧方式到終結狀態方式 159
6.2.4 從終結狀態方式到空棧方式 162
6.2.5 習題 163
6.3 PDA和CFG的等價性 164
6.3.1 從文法到PDA 164
6.3.2 從PDA到文法 167
6.3.3 習題 170
6.4 確定型PDA 171
6.4.1 確定型PDA的定義 171
6.4.2 正則語言與確定型PDA 172
6.4.3 DPDA與上下文無關語言 173
6.4.4 DPDA與歧義文法 173
6.4.5 習題 174
6.5 小結 175
6.6 參考文獻 175
 
第7章 上下文無關語言的性質 177
7.1 上下文無關文法的範式 177
7.1.1 去除無用的符號 177
7.1.2 計算產生符號和可達符號 179
7.1.3 去除e產生式 180
7.1.4 去除單位產生式 182
7.1.5 喬姆斯基範式 185
7.1.6 習題 189
7.2 上下文無關語言的泵引理 191
7.2.1 語法分析樹的大小 191
7.2.2 泵引理的陳述 191
7.2.3 CFL的泵引理的應用 193
7.2.4 習題 195
7.3 上下文無關語言的封閉性 196
7.3.1 代入 196
7.3.2 代入定理的應用 198
7.3.3 反轉 198
7.3.4 與正則語言的交 199
7.3.5 逆同態 202
7.3.6 習題 204
7.4 CFL的判定性質 205
7.4.1 在CFG和PDA之間相互轉化的複雜性 205
7.4.2 變換到喬姆斯基範式的執行時間 207
7.4.3 測試CFL的空性 207
7.4.4 測試CFL的成員性 209
7.4.5 不可判定的CFL問題一覽 211
7.4.6 習題 211
7.5 小結 212
7.6 參考文獻 212
 
第8章 圖靈機導引 215
8.1 電腦不能解答的問題 215
8.1.1 顯示“hello, world”的程式 215
8.1.2 假設中的“hello, world”檢驗程式 217
8.1.3 把問題歸約到另一個問題 219
8.1.4 習題 221
8.2 圖靈機 221
8.2.1 尋求判定所有數學問題 222
8.2.2 圖靈機的記號 222
8.2.3 圖靈機的暫態描述 223
8.2.4 圖靈機轉移圖 225
8.2.5 圖靈機的語言 227
8.2.6 圖靈機與停機 228
8.2.7 習題 228
8.3 圖靈機的程式設計技術 229
8.3.1 在狀態中存儲 230
8.3.2 多道 231
8.3.3 副程式 232
8.3.4 習題 234
8.4 基本圖靈機的擴展 234
8.4.1 多帶圖靈機 234
8.4.2 單帶圖靈機與多帶圖靈機的等價性 235
8.4.3 執行時間與多帶合一構造 236
8.4.4 非確定型圖靈機 237
8.4.5 習題 239
8.5 受限制的圖靈機 240
8.5.1 具有半無窮帶的圖靈機 240
8.5.2 多堆疊機器 242
8.5.3 計數器機器 244
8.5.4 計數器機器的能力 244
8.5.5 習題 246
8.6 圖靈機與電腦 247
8.6.1 用電腦類比圖靈機 247
8.6.2 用圖靈機類比電腦 248
8.6.3 比較電腦與圖靈機的執行時間 251
8.7 小結 252
8.8 參考文獻 253
 
第9章 不可判定性 255
9.1 非遞迴可枚舉語言 255
9.1.1 枚舉二進位串 256
9.1.2 圖靈機編碼 256
9.1.3 對角化語言 257
9.1.4 證明Ld 非遞迴可枚舉 258
9.1.5 習題 258
9.2 遞迴可枚舉但不可判定的問題 259
9.2.1 遞迴語言 259
9.2.2 遞迴語言和遞迴可枚舉語言的補 260
9.2.3 通用語言 262
9.2.4 通用語言的不可判定性 263
9.2.5 習題 264
9.3 與圖靈機有關的不可判定問題 266
9.3.1 歸約 266
9.3.2 接受空語言的圖靈機 267
9.3.3 萊斯定理與遞迴可枚舉語言的性質 269
9.3.4 與圖靈機說明有關的問題 271
9.3.5 習題 272
9.4 波斯特對應問題 272
9.4.1 波斯特對應問題的定義 273
9.4.2 “修改過的”PCP 274
9.4.3 PCP不可判定性證明之完成 276
9.4.4 習題 281
9.5 其他不可判定問題 281
9.5.1 與程式有關的問題 281
9.5.2 CFG歧義性問題 281
9.5.3 表語言的補 283
9.5.4 習題 285
9.6 小結 285
9.7 參考文獻 286
 
第10章 難解問題 289
10.1 P類和NP類 289
10.1.1 可在多項式時間內解答的問題 290
10.1.2 例子：克魯斯卡爾演算法 290
10.1.3 非確定型多項式時間 293
10.1.4 NP例子：貨郎問題 293
10.1.5 多項式時間歸約 294
10.1.6 NP 問題 295
10.1.7 習題 296
10.2 NP 問題 297
10.2.1 可滿足性問題 297
10.2.2 表示SAT實例 299
10.2.3 SAT問題的NP 性 299
10.2.4 習題 304
10.3 約束可滿足性問題 304
10.3.1 布林運算式的範式 304
10.3.2 把運算式轉化成CNF 305
10.3.3 CSAT的NP 性 308
10.3.4 3SAT的NP 性 311
10.3.5 習題 312
10.4 其他的NP 問題 312
10.4.1 描述NP 問題 313
10.4.2 獨立集問題 313
10.4.3 頂點覆蓋問題 316
10.4.4 有向哈密頓回路問題 317
10.4.5 無向哈密頓回路與TSP 322
10.4.6 NP 問題小結 323
10.4.7 習題 323
10.5 小結 326
10.6 參考文獻 326
 
第11章 其他問題類 329
11.1 NP 中的語言的補 330
11.1.1 NP 補語言類 330
11.1.2 NP 問題與 NP 補 330
11.1.3 習題 331
11.2 在多項式空間內可解決的問題 331
11.2.1 多項式空間圖靈機 332
11.2.2 PS 和 NPS 與前面定義的類的關係 332
11.2.3 確定型多項式空間與非確定型多項式空間 333
11.3 對 PS 的問題 335
11.3.1 PS 性 335
11.3.2 帶量詞的布林公式 336
11.3.3 帶量詞的布林公式的求值 337
11.3.4 QBF問題的PS 性 338
11.3.5 習題 341
11.4 基於隨機化的語言類 342
11.4.1 快速排序：隨機演算法舉例 342
11.4.2 隨機化的圖靈機模型 343
11.4.3 隨機化圖靈機的語言 344
11.4.4 RP 類 345
11.4.5 識別 RP 語言 347
11.4.6 ZPP 類 348
11.4.7 RP 與 ZPP 之間的關係 348
11.4.8 與 P 類和 NP 類的關係 349
11.5 素數性測試的複雜性 349
11.5.1 素數性測試的重要性 350
11.5.2 同餘算術簡介 351
11.5.3 同餘算術計算的複雜性 352
11.5.4 隨機多項式素數性測試 353
11.5.5 非確定型素數性測試 354
11.5.6 習題 356
11.6 小結 356
11.7 參考文獻 357
索引 359