第1章 基礎知識
1.1 集合, 關系和函數
1.2 證明方法
1.3 圖
1.4 語言：基本概念
問題與解答
習題
第2章 文法
2.1 文法的定義和分類
2.2 二義性
2.3 CFG 的化簡
2.4 范式
問題和解答
習題
第3章 有限狀態自動機
3.1 確定有限狀態自動機(DFSA)
3.2 不確定有限狀態自動機(NFSA)
3.3 正則表達式
問題與解答
習題
第4章 有限自動機：特征、性質和可判定性
4.1 有限自動機和正則文法
4.2 正則集的泵浦引理
4.3 封閉性
4.4 可判定性定理
問題和解答
習題
第5章 帶輸出的有限狀態自動機及其最小化
5.1 Myhill鄄Nerode 定理
5.2 帶輸出的有限自動機
問題與解答
習題
第6章 有限自動機的變形
6.1 雙向有限自動機
6.2 多頭有限狀態自動機
6.3 概率有限自動機
6.4 加權有限自動機和數字圖像
問題與解答
習題
第7章 下推自動機
7.1 下推自動機
7.2 空棧接受和終態接受的等價
7.3 CFG 和PDA 的等價
問題與解答
習題
第8章 上下文無關文法性質與分析
8.1 CFL 的泵引理
8.2 CFL 的封閉性
8.3 CFL 的判定性質
8.4 CFL 的子群
8.5 帕里克映射與帕里克定理
8.6 自嵌入性
8.7 同態下的特性
問題與解答
習題
第9章 圖靈機
9.1 作為接受器的圖靈機
9.2 作為計算設備的圖靈機
9.3 圖靈機的構造技術
問題與解答
習題
第10章 圖靈機的變形
10.1 通用版本
10.2 受限圖靈機
10.3 作為枚舉器的圖靈機
10.4 圖靈機和0 型語言的等價
10.5 線性有界自動機
10.6 歌德爾編號
問題與解答
習題
第11章 通用圖靈機及可判定性
11.1 圖靈機的編碼和枚舉
11.2 遞歸和遞歸可枚舉集
11.3 通用圖靈機
11.4 問題, 實例和語言
11.5 萊斯定理
11.6 規約問題以證明不可判定性
11.7 波斯特對應問題
11.8 可計算函數
問題與解答
習題
第12章 時間與空間復雜度
12.1 RAM 模型
12.2 圖靈機的時間與帶復雜度
問題與解答
習題
第13章 最近的趨勢及應用
13.1 正則重寫
13.2 馬庫斯上下文文法
13.3 林登麥伊爾系統
13.4 文法系統及分布式自動機
第14章 一些新的計算模型
14.1 DNA 計算
14.2 膜計算
單項選擇題(I)
新書資訊