译者序(Ⅲ)

第一版序言(Ⅴ)

第二版序言(Ⅶ)

导言(Ⅸ)

第１章集合、关系和语言(１)

１１集合(１)

１２关系与函数(４)

１３特殊类型的二元关系(７)

１４有穷集合与无穷集合(１１)

１５三个基本的证明技术(１３)

１６闭包与算法(１７)

１７字母表与语言(２５)

１８语言的有穷表示(２９)

参考文献(33)

第２章有穷自动机(３４)

２１确定型有穷自动机(３４)

２２非确定型有穷自动机(３９)

２３有穷自动机与正则表达式(４７)

２４正则语言与非正则语言(５４)

２５状态最小化(５８)

２６关于有穷自动机的算法(６５)

参考文献(７０)

第３章上下文无关语言(７２)

３１上下文无关文法(７２)

３２语法分析树(７９)

３３下推自动机(８３)

３４下推自动机与上下文无关文法(８７)

３５上下文无关语言与非上下文无关语言(９２)

３６关于上下文无关文法的算法(９７)

３７确定性与语法分析(１０２)

参考文献(１１５)

第４章Ｔuring机(１１７)

４１Ｔuring机的定义(１１７)

４２用Ｔuring机计算(１２５)

４３Ｔ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)