計(jì)算理論基礎(chǔ)（第2版）

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