目錄
第1章 基礎(chǔ)知識(shí) 1
1.1 集合及其運(yùn)算 1
1.2 關(guān)系 3
1.2.1 二元關(guān)系 3
1.2.2 等價(jià)關(guān)系 3
1.2.3 關(guān)系合成 4
1.3 證明和證明的方法 5
1.3.1 反證法 5
1.3.2 歸納法 6
1.3.3 遞歸的定義與歸納證明 7
1.4 圖與樹(shù) 7
1.5 語(yǔ)言 8
1.6 常用術(shù)語(yǔ) 8
1.7 形式語(yǔ)言與自動(dòng)機(jī)的發(fā)展 11
習(xí)題1 13
第2章 形式語(yǔ)言 14
2.1 例子語(yǔ)言 14
2.2 文法和語(yǔ)言的關(guān)系 19
2.2.1 文法 19
2.2.2 語(yǔ)言 21
2.2.3 文法和語(yǔ)言的3類問(wèn)題 22
2.3 Chomsky對(duì)文法和語(yǔ)言的分類 23
2.4 文法產(chǎn)生語(yǔ)言 27
2.5 無(wú)用非終結(jié)符 35
2.6 推導(dǎo)樹(shù) 35
2.7 空串定理 38
2.8 消除左遞歸 39
2.8.1 消除直接左遞歸 39
2.8.2 消除間接左遞歸 40
2.9 上下文無(wú)關(guān)文法的另一種表示 42
2.10 語(yǔ)言之間的運(yùn)算及運(yùn)算的封閉性 43
2.10.1 語(yǔ)言之間的基本運(yùn)算 43
2.10.2 語(yǔ)言之間的運(yùn)算的封閉性 44
2.10.3 語(yǔ)言之間的其他運(yùn)算 48
2.11 正則表達(dá)式和正則集 50
習(xí)題2 53
第3章 有限狀態(tài)自動(dòng)機(jī) 55
3.1 有限狀態(tài)自動(dòng)機(jī)簡(jiǎn)介 55
3.2 確定有限狀態(tài)自動(dòng)機(jī)接收的語(yǔ)言 57
3.3 確定有限狀態(tài)自動(dòng)機(jī)接收語(yǔ)言的例子 62
3.4 不確定有限狀態(tài)自動(dòng)機(jī) 74
3.4.1 不確定有限狀態(tài)自動(dòng)機(jī)簡(jiǎn)介 75
3.4.2 不確定有限狀態(tài)自動(dòng)機(jī)的確定化 76
3.5 帶有ε動(dòng)作的有限狀態(tài)自動(dòng)機(jī) 82
3.6 有限狀態(tài)自動(dòng)機(jī)的一些變形 89
3.6.1 雙向的有限狀態(tài)自動(dòng)機(jī) 89
3.6.2 帶有輸出的有限狀態(tài)自動(dòng)機(jī) 90
3.7 有限狀態(tài)接收機(jī)的存儲(chǔ)技術(shù) 94
3.8 有限狀態(tài)自動(dòng)機(jī)應(yīng)用實(shí)例 96
習(xí)題3 109
第4章 下推自動(dòng)機(jī) 110
4.1 下推自動(dòng)機(jī)簡(jiǎn)介 110
4.1.1 確定的下推自動(dòng)機(jī) 111
4.1.2 不確定的下推自動(dòng)機(jī) 114
4.1.3 下推自動(dòng)機(jī)接收語(yǔ)言的兩種方式 116
4.1.4 廣義下推自動(dòng)機(jī)和單態(tài)下推自動(dòng)機(jī) 120
4.2 上下文無(wú)關(guān)文法和范式 123
4.2.1 Chomsky范式 123
4.2.2 Greibach范式 124
4.3 下推自動(dòng)機(jī)與上下文無(wú)關(guān)語(yǔ)言 126
4.4 下推自動(dòng)機(jī)應(yīng)用實(shí)例 138
習(xí)題4 141
第5章 圖靈機(jī) 143
5.1 圖靈機(jī)的基本模型 143
5.1.1 圖靈機(jī)的定義 143
5.1.2 圖靈機(jī)的構(gòu)造 146
5.2 圖靈機(jī)作為非負(fù)整數(shù)函數(shù)計(jì)算模型 153
5.3 圖靈機(jī)的構(gòu)造技術(shù) 156
5.3.1 圖靈機(jī)的存儲(chǔ)技術(shù) 156
5.3.2 圖靈機(jī)的移動(dòng)技術(shù) 160
5.3.3 圖靈機(jī)掃描多個(gè)符號(hào)技術(shù) 161
5.3.4 圖靈機(jī)的多道技術(shù) 173
5.3.5 圖靈機(jī)的查訖技術(shù) 180
5.3.6 圖靈機(jī)的子程序技術(shù) 181
5.4 圖靈機(jī)變形 184
5.4.1 雙向無(wú)窮帶圖靈機(jī) 185
5.4.2 多帶多讀/寫(xiě)頭圖靈機(jī) 188
5.4.3 不確定圖靈機(jī) 189
5.4.4 多維圖靈機(jī) 191
5.4.5 其他圖靈機(jī) 192
5.5 通用圖靈機(jī) 195
5.5.1 編碼目的 195
5.5.2 編碼方法 195
5.5.3 總結(jié) 198
5.6 圖靈機(jī)與短語(yǔ)結(jié)構(gòu)語(yǔ)言 198
5.7 線性有界的圖靈機(jī)與上下文相關(guān)語(yǔ)言 198
5.8 圖靈機(jī)應(yīng)用實(shí)例 199
習(xí)題5 205
參考文獻(xiàn) 207