《自動機理論與套用》是2009年清華大學出版社出版的圖書，作者是里奇。
基本介紹
- 書名：自動機理論與套用
- 作者：里奇
- ISBN：9787302212935
- 定價：99.00 元
- 出版社：清華大學出版社
- 出版時間： 2009年11月
- 開本：16開
內容簡介,圖書目錄,
內容簡介
《自動機理論與套用(影印版)》闡述了計算科學的優美理論基礎，通過演示計算理論在現代硬體和軟體系統設計中的影響，把理論知識帶到了現實實踐之中。《自動機理論與套用(影印版)》介紹了關鍵概念的套用，為讀者在實際工作中使用計算理論提供實際指導。《自動機理論與套用(影印版)》討論的套用包括：程式設計語言、編譯器、網路技術、自然語言處理、人工智慧、計算生物學、安全性、博弈、商業規則建模、標識語言、Web搜尋等。《自動機理論與套用(影印版)》既適合作為自動機理論課程的教程，也是相關專業人員的重要參考用書。
圖書目錄
第1部分 簡 介
第1章 為什麼學習計算理論 3
1.1 編程工具的歷史 3
1.2 理論的套用無處不在 5
第2章 語言與字元串 7
2.1 字元串 7
2.1.1 字元串函式 7
2.1.2 字元串的關係 8
2.2 語言 9
2.2.1 定義語言的方法 9
2.2.2 語言的勢 11
2.2.3 有多少語言 11
2.2.4 語言函式 12
2.2.5 對語言字元串賦予意義 14
練習 15
第3章 語言層次 16
3.1 定義任務：語言識別 16
3.2 編碼的力量 16
3.2.1 一切都是字元串 16
3.2.2 把問題變成決策問題 19
3.3 基於機器的語言類層次 20
3.3.1 正則語言 20
3.3.2 上下文無關語言 21
3.3.3 可確定和半確定語言 22
3.3.4 計算層次及其重要性 23
3.4 語言類的可跟蹤性層次 24
練習 25
第4章 計算 26
4.1 決策過程 26
4.2 確定性與非確定性 29
4.3 語言與程式的函式 33
練習 35
第2部分 有限狀態機與正則語言
第5章 有限狀態機 39
5.1 確定性有限狀態機 40
5.2 正則語言 43
5.3 設計確定性有限狀態機 44
5.4 非確定性FSM 46
5.4.1 什麼是非確定性FSM 47
5.4.2 模式與子串匹配的NDFSM 49
5.4.3 分析非確定FSM 50
5.4.4 確定FSM與非確定FSM的等價性 52
5.5 從FSM到作業系統 56
5.6 FSM模擬 56
5.6.1 模擬確定FSM 56
5.6.2 模擬非確定FSM 57
5.7 簡化FSM 58
5.7.1 建立一種語言的最簡DFSM 58
5.7.2 簡化DFSM 63
5.8 正則語言的規範形式 66
5.9 有限狀態變換器 67
5.10 雙向變換器 69
5.11 隨機有限自動機：Markov模型與隱藏Markov模型 70
5.11.1 Markov模型 71
5.11.2 隱馬模型 74
5.12 有限自動機、無限字元串：Büchi自動機 79
練習 83
第6章 正則表達式 88
6.1 什麼是正則表達式 88
6.2 Kleene定理 91
6.2.1 建立正則表達式的FSM 92
6.2.2 從FSM建立正則表達式 94
6.2.3 正則表達式與FSM的等價性 99
6.2.4 Kleene定理、正則表達式和有限狀態機 99
6.3 套用正則表達式 102
6.4 操縱和簡化正則表達式 103
練習 105
第7章 正則文法 108
7.1 正則文法的定義 108
7.2 正則文法與正則語言 109
練習 112
第8章 正則與非正則語言 113
8.1 有多少正則語言 113
8.2 證明一個語言是正則語言 113
8.3 正則語言的一些閉包屬性 115
8.4 證明一個語言不是正則 117
8.4.1 正則語言的泵定理 118
8.4.2 使用閉包屬性 122
8.5 利用問題特定知識 123
8.6 正則語言的函式 124
練習 126
第9章 正則語言的算法與決策過程 130
9.1 基本決策過程 130
9.1.1 成員關係 130
9.1.2 空性與整體性 131
9.1.3 有限性 133
9.1.4 等價性 134
9.1.5 最簡性 134
9.1.6 綜合回答特定問題 135
9.2 正則語言算法與決策過程小結 135
練習 136
第10章 小結與參考資料 138
參考資料 139
第3部分 上下文無關語言與壓棧自動機
第11章 上下文無關文法 143
11.1 改寫系統與文法簡介 143
11.2 上下文無關文法與語言 145
11.3 設計上下文無關文法 149
11.4 簡化上下文無關文法 150
11.5 證明文法正確 151
11.6 推導與解析樹 154
11.7 歧義性 155
11.7.1 歧義性有什麼問題 156
11.7.2 固有歧義性 157
11.7.3 消歧文法 158
11.8 範式 164
11.8.1 文法的範式 164
11.8.2 變成範式 165
11.8.3 變成Chomsky範式 166
11.8.4 範式的代價 170
11.9 孤島文法 170
11.10 隨機上下文無關文法 172
練習 173
第12章 壓棧自動機 177
12.1 非確定性壓棧自動機的定義 177
12.2 確定性與非確定性PDA 180
12.2.1 確定性PDA的定義 180
12.2.2 了解非確定性 181
12.2.3 減少非確定性 183
12.3 上下文無關文法與PDA的等價性 184
12.3.1 建立一個文法的PDA 184
12.3.2 建立一個PDA的文法 188
12.3.3 上下文無關文法與PDA的等價性 193
12.4 非確定性與停機 193
12.5 PDA的其他等價定義 195
12.6 不等價於PDA的情形 196
練習 196
第13章 上下文無關與非上下文無關語言 197
13.1 上下文無關語言的地位 197
13.2 證明一種語言為上下文無關語言 198
13.3 上下文無關語言的泵定理 198
13.4 上下文無關語言一些重要閉包屬性 203
13.4.1 閉包定理 203
13.4.2 泵定理和閉合屬性一起使用 205
13.5 確定性上下文無關語言 207
13.6 Ogden推論 213
13.7 Parikh定理 215
13.8 上下文無關語言函式 217
練習 218
第14章 上下文無關語言的算法與決策過程 222
14.1 可確定問題 222
14.1.1 成員關係 222
14.1.2 空性與有限性 225
14.1.3 確定性上下文無關語言的相等性 226
14.2 不可確定問題 226
14.3 上下文無關語言算法與決策過程小結 226
練習 227
第15章 上下文無關解析 228
15.1 辭典分析 229
15.2 自頂向下解析 230
15.2.1 深度優先搜尋 231
15.2.2 修改自頂向下解析的文法 233
15.2.3 確定性自頂向下解析與LL(1)文法 237
15.3 自下而上解析 240
15.3.1 Cocke-Kasami-Younger算法 240
15.3.2 上下文無關解析與矩陣乘法 243
15.3.3 移位減少解析 243
15.3.4 確定性自下而上LR解析 247
15.4 解析自然語言 248
15.4.1 問題 248
15.4.2 Earley算法 248
練習 254
第16章 小結與參考資料 255
參考資料 255
第4部分 圖靈機與不可確定性
第17章 圖靈機 259
17.1 定義、符號與例子 259
17.1.1 什麼是圖靈機 259
17.1.2 圖靈機編程 262
17.1.3 停機 263
17.1.4 形式化圖靈機操作 263
17.1.5 圖靈機的宏記法 264
17.2 用圖靈機計算 267
17.2.1 用圖靈機作為語言識別器 267
17.2.2 圖靈機計算函式 270
17.3 增加多個磁帶和非確定性 272
17.3.1 多帶 272
17.3.2 非確定性圖靈機 276
17.4 模擬實際計算機 279
17.5 其他圖靈機定義 282
17.5.1 單向與雙向無限帶 282
17.5.2 堆疊與磁帶 283
17.6 將圖靈機編碼成字元串 284
17.6.1 圖靈機編碼模式 285
17.6.2 枚舉圖靈機 286
17.6.3 編碼的另一個好處 287
17.6.4 編碼一個圖靈機的多個輸入 287
17.7 萬能圖靈機 288
練習 289
第18章 Church-Turing命題 293
18.1 命題 293
18.2 等價形式例子 295
18.2.1 現代計算機 295
18.2.2 Lambda演算 295
18.2.3 標註系統 296
18.2.4 Post生產系統 296
18.2.5 無限制文法 297
18.2.6 Markov算法 298
18.2.7 Conway生命遊戲 299
18.2.8 一維基本元胞自動機 299
18.2.9 DNA計算 300
練習 301
第19章 停止問題的不可解決性 303
19.1 語言H是半確定的但不是確定的 304
19.2 H不可確定性的一些意義 306
19.3 回到圖靈、Church和決策問題 307
練習 308
第20章 可確定與半確定語言 309
20.1 D概述 309
20.2 SD概述 309
20.3 D與SD之間的子集關係 310
20.4 D與SD類的補集 311
20.5 枚舉語言 312
20.5.1 按未定義順序枚舉 312
20.5.2 辭典順序枚舉 314
20.6 小結 315
練習 316
第21章 可確定性與不可確定性證明 318
21.1 歸約法 318
21.2 用歸約法證明一個語言不是可確定的 320
21.2.1 映射歸約性 322
21.2.2 不是映射歸約的歸約 329
21.3 是不是圖靈機的所有問題都不可確定 330
21.4 Rice定理 331
21.5 實際程式的不可確定問題 334
21.6 證明一個語言不是半確定 336
21.6.1 非歸約法 336
21.6.2 歸約法 337
21.6.3 L是否在D、SD/D或?SD 341
21.7 包括圖靈機描述的D、SD/D和?SD語言小結 341
練習 342
第22章 不明顯提圖靈機問題的語言的可確定性 345
22.1 Diophantine方程與Hilbert第十問題 345
22.2 Post對應性問題 346
22.3 鋪磚問題 348
22.4 邏輯理論 350
22.4.1 布爾理論 351
22.4.2 一階邏輯理論 351
22.5 上下文無關語言的不可確定問題 353
22.5.1 通過計算歷史歸約 354
22.5.2 使用CFGALL的不可確定性 356
22.5.3 從PCP歸約 357
練習 359
第23章 無限制文法 361
23.1 定義和例子 361
23.2 非限制文法與圖靈機的等價性 365
23.3 文法計算函式 366
23.4 無限制文法的不可確定問題 368
23.5 半Thue系統的單詞問題 369
練習 370
第24章 Chomsky層次及其他 371
24.1 上下文有關語言 371
24.1.1 線性有界自動機確定 372
24.1.2 上下文有關文法 373
24.1.3 線性有界自動機與上下文有關文法的等價性 374
24.1.4 上下文有關語言在語言層次中的位置 374
24.1.5 上下文有關語言的閉包屬性 376
24.1.6 上下文有關語言的決策過程 378
24.2 Chomsky層次 380
24.3 屬性、特性與合一文法 381
24.4 Lindenmayer系統 383
練習 389
第25章 可計算函式 391
25.1 什麼是可計算函式 391
25.1.1 總體與部分函式 391
25.1.2 部分可計算與可計算函式 392
25.1.3 不是部分可計算的函式 394
25.1.4 忙海狸函式 395
25.1.5 語言與函式 397
25.2 遞歸函式理論 398
25.2.1 基本遞歸函式 398
25.2.2 Ackermann函式 400
25.2.3 可遞歸（可計算）函式 401
25.3 遞歸定理及其使用 403
練習 408
第26章 小結與參考資料 410
參考資料 411
第5部分 復 雜 度
第27章 複雜度分析簡介 415
27.1 旅行銷售員問題 415
27.2 複雜度0 416
27.3 問題特性化 417
27.3.1 選擇編碼方式 417
27.3.2 把最佳化問題變成語言 419
27.4 測量時間與空間複雜度 419
27.4.1 選擇計算模型 419
27.4.2 定義測量時間與空間要求的函式 420
27.5 函式增長速率 422
27.6 漸近優勢 423
27.7 算法空白 427
27.8 例子 427
27.8.1 多項式加速 427
27.8.2 將指數級算法變成多項式算法 433
27.8.3 時間空間取捨 434
練習 435
第28章 時間複雜度類 439
28.1 語言類P 439
28.1.1 P在補集下閉合 439
28.1.2 屬於P的語言 440
28.1.3 正則下上下文無關語言 441
28.1.4 連通圖 441
28.1.5 歐拉路徑與線路 442
28.1.6 最小生成樹 444
28.1.7 質數性測試 446
28.2 語言類NP 447
28.2.1 定義NP類 447
28.2.2 NP語言 449
28.2.3 TSP 451
28.2.4 集團探測 451
28.2.5 布爾可滿足性 452
28.3 P=NP？ 453
28.4 用歸約法進行複雜度證明 454
28.5 NP完備性與Cook-Levin定理 456
28.5.1 NP完備與NP難語言 457
28.5.2 Cook-Levin定理和SAT的NP完備性 458
28.6 其他NP完備問題 462
28.6.1 NP完備問題採樣 462
28.6.2 證明一個語言為NP完備 463
28.6.3 3-SAT 464
28.6.4 獨立集合 465
28.6.5 VERTEX-COVER（頂點覆蓋） 465
28.6.6 哈密爾頓線路與旅行銷售員問題 467
28.7 P與NP完備的關係 473
28.7.1 P與NP完備間的空白 473
28.7.2 兩個類似的線路問題 474
28.7.3 兩個類似的SAT問題 474
28.7.4 兩個類似的路徑問題 474
28.7.5 兩個相似的覆蓋問題 475
28.7.6 三個類似的地圖作色問題 476
28.7.7 兩個類似的線性編程問題 477
28.7.8 Diophantine方程問題的層次 478
28.8 Co-NP語言類 478
28.9 時間層次定理、EXPTIME及其他 479
28.9.1 時間層次定理 480
28.9.2 EXPTIME 483
28.9.3 比EXPTIME更難的問題 484
28.10 FP與FNP問題類 484
練習 485
第29章 空間複雜度類 490
29.1 分析空間複雜度類 490
29.1.1 例子 490
29.1.2 時間與空間複雜度關係 492
29.2 PSPACE、NPSPACE與Savitch定理 493
29.3 PSPACE完備性 496
29.3.1 QBF語言 497
29.3.2 QBF是PSPACE完備的 498
29.3.3 其他PSPACE難題與PSPACE完備問題 501
29.4 次線性空間複雜度 502
29.5 空間複雜度類在補集下閉合 505
29.6 空間層次定理 506
第30章 難題的實用解 508
30.1 方法 508
30.2 隨機算法和BPP、RP、Co-RP與ZPP語言類 509
30.2.1 隨機算法 509
30.2.2 語言類BPP、RP、Co-RP與ZPP 510
30.2.3 測試質數性 513
30.3 啟發式搜尋 515
30.3.1 啟發式搜尋簡介 515
30.3.2 A*算法 517
練習 521
第31章 小結與參考資料 523
參考資料 523
