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