计算理论基础（第2版）

译者序(Ⅲ)
第一版序言(Ⅴ)
第二版序言(Ⅶ)
导言(Ⅸ)
第1章集合、关系和语言(１)
１.１集合(１)
１.2关系与函数(４)
１.３特殊类型的二元关系(７)
１.４有穷集合与无穷集合(１１)
１.５三个基本的证明技术(１３)
１.６闭包与算法(１７)
１.７字母表与语言(２５)
１.８语言的有穷表示(２９)
参考文献(33)
第２章有穷自动机(３４)
２.１确定型有穷自动机(３４)
２.２非确定型有穷自动机(３９)
２.３有穷自动机与正则表达式(４７)
２.４正则语言与非正则语言(５４)
２.５状态最小化(５８)
２.６关于有穷自动机的算法(６５)
参考文献(７０)
第３章上下文无关语言(７２)
３.１上下文无关文法(７２)
３.２语法分析树(７９)
３.３下推自动机(８３)
３.４下推自动机与上下文无关文法(８７)
３.５上下文无关语言与非上下文无关语言(９２)
３.６关于上下文无关文法的算法(９７)
３.７确定性与语法分析(１０２)
参考文献(１１５)
第４章Ｔuring机(１１７)
４.１Ｔuring机的定义(１１７)
４.２用Ｔuring机计算(１２５)
４.3Ｔuring机的扩充(１３０)
４.４随机存取Ｔuring机(１３６)
４.５非确定型Ｔuring机(１４４)
４.６文法(１４８)
４.７数值函数(１５１)
参考文献(１５８)
第５章不可判定性(160)
５.１ChurchＴuring论题(160)
５.２通用Ｔuring机(161)
５.３停机问题(163)
５.４与Ｔuring机有关的不可判定问题(166)
５.５与文法有关的不可解问题(168)
５.６不可解的铺砖问题(172)
５.７递归语言的性质(174)
参考文献(178)
第６章计算复杂性(179)
６.１P类(179)
６.２若干问题(181)
６.３布尔可满足性(187)
６.４NP类(190)
参考文献(194)
第７章NP完全性(196)
７.１多项式时间归约(196)
７.２Cook定理(202)
７.３其他的NP完全问题(207)
７.４对付NP完全性(218)
参考文献(229)
中英对照名词索引(231)