計算理論基礎（第2版）

譯者序                  
 第一版序言                  
 第二版序言                  
 導言                  
 第1章  集合. 關系和語言                  
 1. 1  集合                  
 1. 2  關系與函數(shù)                  
 1. 3  特殊類型的二元關系                  
 1. 4  有窮集合與無窮集合                  
 1. 5  三個基本的證明技術                  
 1. 6  閉包與算法                  
 1. 7  字母表與語言                  
 1. 8  語言的有窮表示                  
 參考文獻                  
 第2章 有窮自動機                  
 2. 1  確定型有窮自動機                  
 2. 2  非確定型有窮自動機                  
 2. 3  有窮自動機與正則表達式                  
 2. 4  正則語言與非正則語言                  
 2. 5  狀態(tài)最小化                  
 2. 6  關于有窮自動機的算法                  
 參考文獻                  
 第3章  上下文無關語言                  
 3. 1  上下文無關文法                  
 3. 2  語法分析樹                  
 3. 3  下推自動機                  
 3. 4  下推自動機與上下文無關文法                  
 3. 5  上下文無關語言與非上下文無關語言                  
 3. 6  關于上下文無關文法的算法                  
 3. 7  確定性與語法分析                  
 參考文獻                  
 第4章  Turing機                  
 4. 1  Turing機的定義                  
 4. 2  用Turing機計算                  
 4. 3  Turing機的擴充                  
 4. 4  隨機存取Turing機                  
 4. 5  非確定型Turing機                  
 4. 6  文法                  
 4. 7  數(shù)值函數(shù)                  
 參考文獻                  
 第5章  不可判定性                  
 5. 1  Church-Turing論題                  
 5. 2  通用Turing機                  
 5. 3  停機問題                  
 5. 4  與Turing機有關的不可判定問題                  
 5. 5  與文法有關的不可解問題                  
 5. 6  不可解的鋪磚問題                  
 5. 7  遞歸語言的性質(zhì)                  
 參考文獻                  
 第6章  計算復雜性                  
 6. 1  P類                  
 6. 2  若干問題                  
 6. 3  布爾可滿足性                  
 6. 4  NP類                  
 參考文獻                  
 第7章  NP完全性                  
 7. 1  多項式時間歸約                  
 7. 2  Cook定理                  
 7. 3  其他的NP完全問題                  
 7. 4  對付NP完全性                  
 參考文獻                  
 中英對照名詞索引