自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論（原書第2版）

出版者的話
專家指導(dǎo)委員會(huì)
譯者序
前言
第1章 自動(dòng)機(jī)：方法與體驗(yàn)
1.1 為什么研究自動(dòng)機(jī)理論
1.1.1 有窮自動(dòng)機(jī)簡(jiǎn)介
1.1.2 結(jié)構(gòu)表示法
1.1.3 自動(dòng)機(jī)與復(fù)雜性
1.2 形式化證明簡(jiǎn)介
1.2.1 演繹證明
1.2.2 求助于定義
1.2.3 其他定理形式
1.2.4 表面上不是“如果-則”命題的定理
1.3 其他的證明形式
1.3.1 證明集合等價(jià)性
1.3.2 逆否命題
1.3.3 反證法
1.3.4 反例
1.4 歸納證明
1.4.1 整數(shù)上的歸納法
1.4.2 更一般形式的整數(shù)歸納法
1.4.3 結(jié)構(gòu)歸納法
1.4.4 互歸納法
1.5 自動(dòng)機(jī)理論的中心概念
1.5.1 字母表
1.5.2 串
1.5.3 語(yǔ)言
1.5.4 問(wèn)題
1.6 小結(jié)
1.7 參考文獻(xiàn)
第2章 有窮自動(dòng)機(jī)
2.1 有窮自動(dòng)機(jī)的非形式化描述
2.1.1 基本規(guī)則
2.1.2 協(xié)議
2.1.3 允許自動(dòng)機(jī)忽略動(dòng)作
2.1.4 整個(gè)系統(tǒng)成為一個(gè)自動(dòng)機(jī)
2.1.5 用乘積自動(dòng)機(jī)驗(yàn)證協(xié)議
2.2 確定型有窮自動(dòng)機(jī)
2.2.1 確定型有窮自動(dòng)機(jī)的定義
2.2.2 DFA如何處理串
2.2.3 DFA的簡(jiǎn)化記號(hào)
2.2.4 把轉(zhuǎn)移函數(shù)擴(kuò)展到串
2.2.5 DFA的語(yǔ)言
2.2.6 習(xí)題
2.3 非確定型有窮自動(dòng)機(jī)
2.3.1 非確定型有窮自動(dòng)機(jī)的非形式化觀點(diǎn)
2.3.2 非確定型有窮自動(dòng)機(jī)的定義
2.3.3 擴(kuò)展轉(zhuǎn)移函數(shù)
2.3.4 NFA的語(yǔ)言
2.3.5 確定型有窮自動(dòng)機(jī)與非確定型有窮自動(dòng)機(jī)的等價(jià)性
2.3.6 子集構(gòu)造的壞情形
2.3.7 習(xí)題
2.4 應(yīng)用：文本搜索
2.4.1 在文本中查找串
2.4.2 文本搜索的非確定型有窮自動(dòng)機(jī)
2.4.3 識(shí)別關(guān)鍵字集合的DFA
2.4.4 習(xí)題
2.5 帶e 轉(zhuǎn)移的有窮自動(dòng)機(jī)
2.5.1 e 轉(zhuǎn)移的用途
2.5.2 e-NFA的形式化定義
2.5.3 e 閉包
2.5.4 e-NFA的擴(kuò)展轉(zhuǎn)移和語(yǔ)言
2.5.5 消除 e 轉(zhuǎn)移
2.5.6 習(xí)題
2.6 小結(jié)
2.7 參考文獻(xiàn)
第3章 正則表達(dá)式與正則語(yǔ)言
3.1 正則表達(dá)式
3.1.1 正則表達(dá)式運(yùn)算符
3.1.2 構(gòu)造正則表達(dá)式
3.1.3 正則表達(dá)式運(yùn)算符的優(yōu)先級(jí)
3.1.4 習(xí)題
3.2 有窮自動(dòng)機(jī)和正則表達(dá)式
3.2.1 從DFA到正則表達(dá)式
3.2.2 通過(guò)消除狀態(tài)把DFA轉(zhuǎn)化為正則表達(dá)式
3.2.3 把正則表達(dá)式轉(zhuǎn)化為自動(dòng)機(jī)
3.2.4 習(xí)題
3.3 正則表達(dá)式的應(yīng)用
3.3.1 UNIX中的正則表達(dá)式
3.3.2 詞法分析
3.3.3 查找文本中的模式
3.3.4 習(xí)題
3.4 正則表達(dá)式代數(shù)定律
3.4.1 結(jié)合律與交換律
3.4.2 單位元與零元
3.4.3 分配律
3.4.4 冪等律
3.4.5 與閉包有關(guān)的定律
3.4.6 發(fā)現(xiàn)正則表達(dá)式定律
3.4.7 檢驗(yàn)正則表達(dá)式代數(shù)定律
3.4.8 習(xí)題
3.5 小結(jié)
3.6 參考文獻(xiàn)
第4章 正則語(yǔ)言的性質(zhì)
4.1 證明語(yǔ)言的非正則性
4.1.1 正則語(yǔ)言的泵引理
4.1.2 泵引理的應(yīng)用
4.1.3 習(xí)題
4.2 正則語(yǔ)言的封閉性
4.2.1 正則語(yǔ)言在布爾運(yùn)算下的閉包
4.2.2 反轉(zhuǎn)
4.2.3 同態(tài)
4.2.4 逆同態(tài)
4.2.5 習(xí)題
4.3 正則語(yǔ)言的判定性質(zhì)
4.3.1 在各種表示之間轉(zhuǎn)化
4.3.2 測(cè)試正則語(yǔ)言的空性
4.3.3 測(cè)試正則語(yǔ)言的成員性
4.3.4 習(xí)題
4.4 自動(dòng)機(jī)的等價(jià)性和最小化
4.4.1 測(cè)試狀態(tài)的等價(jià)性
4.4.2 測(cè)試正則語(yǔ)言的等價(jià)性
4.4.3 DFA最小化
4.4.4 為什么不能比最小DFA更小
4.4.5 習(xí)題
4.5 小結(jié)
4.6 參考文獻(xiàn)
第5章 上下文無(wú)關(guān)文法及上下文無(wú)關(guān)語(yǔ)言
5.1 上下文無(wú)關(guān)文法
5.1.1 一個(gè)非形式化的例子
5.1.2 上下文無(wú)關(guān)文法的定義
5.1.3 使用文法來(lái)推導(dǎo)
5.1.4 最左推導(dǎo)和最右推導(dǎo)
5.1.5 文法的語(yǔ)言
5.1.6 句型
5.1.7 習(xí)題
5.2 語(yǔ)法分析樹
5.2.1 構(gòu)造語(yǔ)法分析樹
5.2.2 語(yǔ)法分析樹的產(chǎn)生
5.2.3 推理、推導(dǎo)和語(yǔ)法分析樹
5.2.4 從推理到樹
5.2.5 從樹到推導(dǎo)
5.2.6 從推導(dǎo)到遞歸推理
5.2.7 習(xí)題
5.3 上下文無(wú)關(guān)文法的應(yīng)用
5.3.1 語(yǔ)法分析器
5.3.2 語(yǔ)法分析器生成器YACC
5.3.3 標(biāo)記語(yǔ)言
5.3.4 XML和文檔類型定義
5.3.5 習(xí)題
5.4 文法和語(yǔ)言的歧義性
5.4.1 歧義文法
5.4.2 去除文法的歧義性
5.4.3 最左推導(dǎo)作為表達(dá)歧義性的一種方式
5.4.4 固有的歧義性
5.4.5 習(xí)題
5.5 小結(jié)
5.6 參考文獻(xiàn)
第6章 下推自動(dòng)機(jī)
6.1 下推自動(dòng)機(jī)的定義
6.1.1 非形式化的介紹
6.1.2 下推自動(dòng)機(jī)的形式化定義
6.1.3 PDA的圖形表示
6.1.4 PDA的瞬時(shí)描述
6.1.5 習(xí)題
6.2 PDA的語(yǔ)言
6.2.1 以終結(jié)狀態(tài)方式接受
6.2.2 以空棧方式接受
6.2.3 從空棧方式到終結(jié)狀態(tài)方式
6.2.4 從終結(jié)狀態(tài)方式到空棧方式
6.2.5 習(xí)題
6.3 PDA和CFG的等價(jià)性
6.3.1 從文法到PDA
6.3.2 從PDA到文法
6.3.3 習(xí)題
6.4 確定型PDA
6.4.1 確定型PDA的定義
6.4.2 正則語(yǔ)言與確定型PDA
6.4.3 DPDA與上下文無(wú)關(guān)語(yǔ)言
6.4.4 DPDA與歧義文法
6.4.5 習(xí)題
6.5 小結(jié)
6.6 參考文獻(xiàn)
第7章 上下文無(wú)關(guān)語(yǔ)言的性質(zhì)
7.1 上下文無(wú)關(guān)文法的范式
7.1.1 去除無(wú)用的符號(hào)
7.1.2 計(jì)算產(chǎn)生符號(hào)和可達(dá)符號(hào)
7.1.3 去除e產(chǎn)生式
7.1.4 去除單位產(chǎn)生式
7.1.5 喬姆斯基范式
7.1.6 習(xí)題
7.2 上下文無(wú)關(guān)語(yǔ)言的泵引理
7.2.1 語(yǔ)法分析樹的大小
7.2.2 泵引理的陳述
7.2.3 CFL的泵引理的應(yīng)用
7.2.4 習(xí)題
7.3 上下文無(wú)關(guān)語(yǔ)言的封閉性
7.3.1 代入
7.3.2 代入定理的應(yīng)用
7.3.3 反轉(zhuǎn)
7.3.4 與正則語(yǔ)言的交
7.3.5 逆同態(tài)
7.3.6 習(xí)題
7.4 CFL的判定性質(zhì)
7.4.1 在CFG和PDA之間互相轉(zhuǎn)化的復(fù)雜性
7.4.2 變換到喬姆斯基范式的運(yùn)行時(shí)間
7.4.3 測(cè)試CFL的空性
7.4.4 測(cè)試CFL的成員性
7.4.5 不可判定的CFL問(wèn)題一覽
7.4.6 習(xí)題
7.5 小結(jié)
7.6 參考文獻(xiàn)
第8章 圖靈機(jī)導(dǎo)引
8.1 計(jì)算機(jī)不能解答的問(wèn)題
8.1.1 顯示“hello, world”的程序
8.1.2 假設(shè)中的“hello, world”檢驗(yàn)程序
8.1.3 把問(wèn)題歸約到另一個(gè)問(wèn)題
8.1.4 習(xí)題
8.2 圖靈機(jī)
8.2.1 尋求判定所有數(shù)學(xué)問(wèn)題
8.2.2 圖靈機(jī)的記號(hào)
8.2.3 圖靈機(jī)的瞬時(shí)描述
8.2.4 圖靈機(jī)轉(zhuǎn)移圖
8.2.5 圖靈機(jī)的語(yǔ)言
8.2.6 圖靈機(jī)與停機(jī)
8.2.7 習(xí)題
8.3 圖靈機(jī)的程序設(shè)計(jì)技術(shù)
8.3.1 在狀態(tài)中存儲(chǔ)
8.3.2 多道
8.3.3 子程序
8.3.4 習(xí)題
8.4 基本圖靈機(jī)的擴(kuò)展
8.4.1 多帶圖靈機(jī)
8.4.2 單帶圖靈機(jī)與多帶圖靈機(jī)的等價(jià)性
8.4.3 運(yùn)行時(shí)間與多帶合一構(gòu)造
8.4.4 非確定型圖靈機(jī)
8.4.5 習(xí)題
8.5 受限制的圖靈機(jī)
8.5.1 具有半無(wú)窮帶的圖靈機(jī)
8.5.2 多堆棧機(jī)器
8.5.3 計(jì)數(shù)器機(jī)器
8.5.4 計(jì)數(shù)器機(jī)器的能力
8.5.5 習(xí)題
8.6 圖靈機(jī)與計(jì)算機(jī)
8.6.1 用計(jì)算機(jī)模擬圖靈機(jī)
8.6.2 用圖靈機(jī)模擬計(jì)算機(jī)
8.6.3 比較計(jì)算機(jī)與圖靈機(jī)的運(yùn)行時(shí)間
8.7 小結(jié)
8.8 參考文獻(xiàn)
第9章 不可判定性
9.1 非遞歸可枚舉語(yǔ)言
9.1.1 枚舉二進(jìn)制串
9.1.2 圖靈機(jī)編碼
9.1.3 對(duì)角化語(yǔ)言
9.1.4 證明Ld 非遞歸可枚舉
9.1.5 習(xí)題
9.2 是遞歸可枚舉但不可判定的問(wèn)題
9.2.1 遞歸語(yǔ)言
9.2.2 遞歸語(yǔ)言和遞歸可枚舉語(yǔ)言的補(bǔ)
9.2.3 通用語(yǔ)言
9.2.4 通用語(yǔ)言的不可判定性
9.2.5 習(xí)題
9.3 與圖靈機(jī)有關(guān)的不可判定問(wèn)題
9.3.1 歸約
9.3.2 接受空語(yǔ)言的圖靈機(jī)
9.3.3 萊斯定理與遞歸可枚舉語(yǔ)言的性質(zhì)
9.3.4 與圖靈機(jī)說(shuō)明有關(guān)的問(wèn)題
9.3.5 習(xí)題
9.4 波斯特對(duì)應(yīng)問(wèn)題
9.4.1 波斯特對(duì)應(yīng)問(wèn)題的定義
9.4.2 “修改過(guò)的”PCP
9.4.3 PCP不可判定性證明之完成
9.4.4 習(xí)題
9.5 其他不可判定問(wèn)題
9.5.1 與程序有關(guān)的問(wèn)題
9.5.2 CFG歧義性問(wèn)題
9.5.3 表語(yǔ)言的補(bǔ)
9.5.4 習(xí)題
9.6 小結(jié)
9.7 參考文獻(xiàn)
第10章 難解問(wèn)題
10.1 P類和NP類
10.1.1 可在多項(xiàng)式時(shí)間內(nèi)解答的問(wèn)題
10.1.2 例子：克魯斯卡爾算法
10.1.3 非確定型多項(xiàng)式時(shí)間
10.1.4 NP例子：貨郎問(wèn)題
10.1.5 多項(xiàng)式時(shí)間歸約
10.1.6 NP完全問(wèn)題
10.1.7 習(xí)題
10.2 NP完全問(wèn)題
10.2.1 可滿足性問(wèn)題
10.2.2 表示SAT實(shí)例
10.2.3 SAT問(wèn)題的NP完全性
10.2.4 習(xí)題
10.3 約束可滿足性問(wèn)題
10.3.1 布爾表達(dá)式的范式
10.3.2 把表達(dá)式轉(zhuǎn)化成CNF
10.3.3 CSAT的NP完全性
10.3.4 3SAT的NP完全性
10.3.5 習(xí)題
10.4 其他的NP完全問(wèn)題
10.4.1 描述NP完全問(wèn)題
10.4.2 獨(dú)立集問(wèn)題
10.4.3 頂點(diǎn)覆蓋問(wèn)題
10.4.4 有向哈密頓回路問(wèn)題
10.4.5 無(wú)向哈密頓回路與TSP
10.4.6 NP完全問(wèn)題小結(jié)
10.4.7 習(xí)題
10.5 小結(jié)
10.6 參考文獻(xiàn)
第11章 其他問(wèn)題類
11.1 NP 中的語(yǔ)言的補(bǔ)
11.1.1 NP 補(bǔ)語(yǔ)言類
11.1.2 NP完全問(wèn)題與 NP 補(bǔ)
11.1.3 習(xí)題
11.2 在多項(xiàng)式空間內(nèi)可解決的問(wèn)題
11.2.1 多項(xiàng)式空間圖靈機(jī)
11.2.2 PS 和 NPS 與前面定義的類的關(guān)系
11.2.3 確定型多項(xiàng)式空間與非確定型多項(xiàng)式空間
11.3 對(duì) PS 完全的問(wèn)題
11.3.1 PS完全性
11.3.2 帶量詞的布爾公式
11.3.3 帶量詞的布爾公式的求值
11.3.4 QBF問(wèn)題的PS完全性
11.3.5 習(xí)題
11.4 基于隨機(jī)化的語(yǔ)言類
11.4.1 快速排序：隨機(jī)算法舉例
11.4.2 隨機(jī)化的圖靈機(jī)模型
11.4.3 隨機(jī)化圖靈機(jī)的語(yǔ)言
11.4.4 RP 類
11.4.5 識(shí)別 RP 語(yǔ)言
11.4.6 ZPP 類
11.4.7 RP 與 ZPP 之間的關(guān)系
11.4.8 與 P 類和 NP 類的關(guān)系
11.5 素?cái)?shù)性測(cè)試的復(fù)雜性
11.5.1 素?cái)?shù)性測(cè)試的重要性
11.5.2 同余算術(shù)簡(jiǎn)介
11.5.3 同余算術(shù)計(jì)算的復(fù)雜性
11.5.4 隨機(jī)多項(xiàng)式素?cái)?shù)性測(cè)試
11.5.5 非確定型素?cái)?shù)性測(cè)試
11.5.6 習(xí)題
11.6 小結(jié)
11.7 參考文獻(xiàn)
索引