計算理論基礎（第2版）

譯者序(Ⅲ)
第一版序言(Ⅴ)
第二版序言(Ⅶ)
導言(Ⅸ)
第1章集合、關系和語言(１)
１.１集合(１)
１.2關系與函數(shù)(４)
１.３特殊類型的二元關系(７)
１.４有窮集合與無窮集合(１１)
１.５三個基本的證明技術(１３)
１.６閉包與算法(１７)
１.７字母表與語言(２５)
１.８語言的有窮表示(２９)
參考文獻(33)
第２章有窮自動機(３４)
２.１確定型有窮自動機(３４)
２.２非確定型有窮自動機(３９)
２.３有窮自動機與正則表達式(４７)
２.４正則語言與非正則語言(５４)
２.５狀態(tài)最小化(５８)
２.６關于有窮自動機的算法(６５)
參考文獻(７０)
第３章上下文無關語言(７２)
３.１上下文無關文法(７２)
３.２語法分析樹(７９)
３.３下推自動機(８３)
３.４下推自動機與上下文無關文法(８７)
３.５上下文無關語言與非上下文無關語言(９２)
３.６關于上下文無關文法的算法(９７)
３.７確定性與語法分析(１０２)
參考文獻(１１５)
第４章Ｔuring機(１１７)
４.１Ｔuring機的定義(１１７)
４.２用Ｔuring機計算(１２５)
４.3Ｔuring機的擴充(１３０)
４.４隨機存?。評ring機(１３６)
４.５非確定型Ｔuring機(１４４)
４.６文法(１４８)
４.７數(shù)值函數(shù)(１５１)
參考文獻(１５８)
第５章不可判定性(160)
５.１ChurchＴuring論題(160)
５.２通用Ｔuring機(161)
５.３停機問題(163)
５.４與Ｔuring機有關的不可判定問題(166)
５.５與文法有關的不可解問題(168)
５.６不可解的鋪磚問題(172)
５.７遞歸語言的性質(zhì)(174)
參考文獻(178)
第６章計算復雜性(179)
６.１P類(179)
６.２若干問題(181)
６.３布爾可滿足性(187)
６.４NP類(190)
參考文獻(194)
第７章NP完全性(196)
７.１多項式時間歸約(196)
７.２Cook定理(202)
７.３其他的NP完全問題(207)
７.４對付NP完全性(218)
參考文獻(229)
中英對照名詞索引(231)