计算理论基础（第2版）

　　计算理论是计算机科学的理论基础。本书介绍了计算理论最核心、最基本的内容，包括形式语言与自动机、可计算性和计算复杂性三大部分。全书共分7章，分别为：集合、关系和语言；有穷自动机；上下文无关语言；Turing机；不可判定性；计算复杂性；NP完全性。本书突出了算法，从而使计算机专业的学生更易于接受，也更有收益。　.本书适合作为计算机专业及数学专业本科生或研究生的教材，也可供从事计算机科学的教学与研究人员参考。...

暂缺《计算理论基础（第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)