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

出版者的話
譯者序
前言
第1章 自動機：方法與體驗
1.1 為什么研究自動機理論
1.1.1 有窮自動機簡介
1.1.2 結(jié)構(gòu)表示法
1.1.3 自動機與復(fù)雜性

1.2 形式化證明簡介
1.2.1 演繹證明
1.2.2 求助于定義
1.2.3 其他定理形式
1.2.4 表面上不是“如果-則”命題的定理

1.3 其他的證明形式
1.3.1 證明集合等價性
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 自動機理論的中心概念
1.5.1 字母表
1.5.2 串
1.5.3 語言
1.5.4 問題
1.6 小結(jié)
1.7 參考文獻

第2章 有窮自動機
2.1 有窮自動機的非形式化描述
2.1.1 基本規(guī)則
2.1.2 協(xié)議
2.1.3 允許自動機忽略動作
2.1.4 整個系統(tǒng)成為一個自動機
2.1.5 用乘積自動機驗證協(xié)議

2.2 確定型有窮自動機
2.2.1 確定型有窮自動機的定義
2.2.2 DFA如何處理串
2.2.3 DFA的簡化記號
2.2.4 把轉(zhuǎn)移函數(shù)擴展到串
2.2.5 DFA的語言
2.2.6 習(xí)題

2.3 非確定型有窮自動機
2.3.1 非確定型有窮自動機的非形式化觀點
2.3.2 非確定型有窮自動機的定義
2.3.3 擴展轉(zhuǎn)移函數(shù)
2.3.4 NFA的語言
2.3.5 確定型有窮自動機與非確定型有窮自動機的等價性
2.3.6 子集構(gòu)造的壞情形
2.3.7 習(xí)題

2.4 應(yīng)用：文本搜索
2.4.1 在文本中查找串
2.4.2 文本搜索的非確定型有窮自動機
2.4.3 識別關(guān)鍵字集合的DFA
2.4.4 習(xí)題

2.5 帶e 轉(zhuǎn)移的有窮自動機
2.5.1 e 轉(zhuǎn)移的用途
2.5.2 e-NFA的形式化定義
2.5.3 e 閉包
2.5.4 e-NFA的擴展轉(zhuǎn)移和語言
2.5.5 消除 e 轉(zhuǎn)移
2.5.6 習(xí)題
2.6 小結(jié)
2.7 參考文獻

第3章 正則表達式與正則語言
3.1 正則表達式
3.1.1 正則表達式運算符
3.1.2 構(gòu)造正則表達式
3.1.3 正則表達式運算符的優(yōu)先級
3.1.4 習(xí)題

3.2 有窮自動機和正則表達式
3.2.1 從DFA到正則表達式
3.2.2 通過消除狀態(tài)把DFA轉(zhuǎn)化為正則表達式
3.2.3 把正則表達式轉(zhuǎn)化為自動機
3.2.4 習(xí)題

3.3 正則表達式的應(yīng)用
3.3.1 UNIX中的正則表達式
3.3.2 詞法分析
3.3.3 查找文本中的模式
3.3.4 習(xí)題

3.4 正則表達式代數(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)正則表達式定律
3.4.7 檢驗正則表達式代數(shù)定律
3.4.8 習(xí)題
3.5 小結(jié)
3.6 參考文獻
第4章 正則語言的性質(zhì)
第5章 上下文無關(guān)文法及上下文無關(guān)語言
第6章 下推自動機
第7章 上下文無關(guān)語言的性質(zhì)
第8章 圖靈機導(dǎo)引
第9章 不可判定性
第10章 難解問題
第11章 其他問題類
索引