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