自動機(jī)理論、語言和計算導(dǎo)論（原書第3版·典藏版）

譯者序
前言
第1章 自動機(jī)：方法與體驗(yàn) 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ī)驗(yàn)證協(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ī)的非形式化觀點(diǎn) 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 檢驗(yàn)正則表達(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.