理论计算机科学是推动计算机技术和应用向前发展的巨大动力。形式语言、自动机、可计算性、计算复杂性和相关方面内容构成的计算理论，是理论计算机科学的基础内容之一。本书由美国莱特州立大学计算机科学及工程系的Thomas A. Sudkamp教授编写，是介绍这些内容的优秀教材。
　　全书不仅介绍了计算机科学的基础，探讨了算法计算的能力和局限；而且还通过概念的严格表述，以及使用通俗的例子来解释定理，从而帮助学生提高数学论证能力。书中每章后面都有一些练习，通过这些练习使学生加深对本章内容的理解。

　　第三版亮点：
　　●超过100个新的习题和示例
　　●强调问题表述和问题归约的重要性
　　●显著地扩展了计算复杂性的覆盖面
　　●增加了用问题归约证明NP完全性的章节
　　●处理NP完全问题时给出了近似算法

无

本书第3版的出版目的与前两版相同，即介绍计算科学理论，从而为计算机专业的初级和中级学生提供计算机科学理论的健全的数学表示。促使我对上一版进行更新的原因有三个：通过提供附加的动机介绍和例子来增强表达效果；扩大知识范围，特别是在计算复杂性这一领域；为教师讲授计算机科学理论的课程提供更多的灵活性。
许多面向应用领域的学生质疑学习理论基础知识的重要性。然而，正是这门课强调了计算机科学问题的宏观视图。现在的编程语言和计算机体系结构很陈旧，另外，与此相关的大家感兴趣的问题都已经找到了相应的解决方案，本书中的很多内容都与这些相关。什么类型的模式可以用某种算法识别？语言如何被形式化地定义和分析？算法计算的固有能力和局限性是什么？有哪些问题的解决方法需要的时间和空间过多以至现实中无法实现？如何比较两个问题相对的困难程度？上述问题在本书中都将逐一论述。
组织
由于绝大多数本科计算机科学专业的学生都没有或缺少足够的抽象数学的基础知识，因此本书不仅介绍计算机科学的基础，而且希望能够提高学生的数学论证能力。我们通过概念的严格表述，以及使用通俗的例子来解释一些定理，来达到上述目的。每章最后都有一些练习，从而强化和加深对本章内容的理解。
为了便于大家学习，我们假设大家都没有特殊的数学预备知识。因而，第1章介绍计算理论的数学工具：基本集合理论、递归定义以及数学归纳证明。除了1.3节和1.4节介绍的特殊内容外，第1章和第2章介绍了覆盖全书的基础知识。1.3节介绍基数和对角化。它们被用在构造不确定语言和不可计算方法的存在性证明中。1.4节检查反证法中的自引用的使用。这种技术用在不确定性证明中，包括证明停机问题无解。对于那些已经学完离散数学课程的学生，第1章的大部分内容可以看作是对这些知识的复习。
考虑到计算基础的不同课程可以强调不同的主题，本书的表述和组织方式设计为允许一门课程深入探究某些特殊主题，同时提供一种加强对主要主题的研究能力，这种能力通过介绍和深入探讨计算机科学理论研究范围的材料来获取。课程的核心内容集中于形式化的自动机语言理论的经典表示，可计算性和不确定性、计算复杂性，以及作为编程语言定义和编译器设计基础的形式化语言，详见下面表格。小节后面的星号表示这部分内容可以略过但并不影响整本书表述的连贯性。带星号的小节通常包括应用的表示、相关主题的介绍或是主题中一个复杂结论的详细证明。

形式语言和自动机理论计算理论　　计算复杂性编程语言的形式语言第1章：1-3，6-8第1章：所有第1章：所有第1章：1-3，6-8第2章：1-3，4*第2章：1-3，4*第2章：1-3，4*第2章：1-4第3章：1-3，4*第5章：1-6，7*第5章：1-4，5-7*第3章：1-4第4章：1-5，6*，7第8章：1-7，8*第8章：1-7，8*第4章：1-5，6*,7第5章：1-6，7*第9章：1-5，6*第9章：1-4，5-6*第5章：1-6，7*第6章：1-5，6*第10章：1第11章：1-4，5*第7章：1-3，4-5*第7章：1-5第11章：所有第14章：1-4，5-7*第18章：所有第8章：1-7，8*第12章：所有第15章：所有第19章：所有第9章：1-5，6*第13章：所有第16章：1-6，7*第20章：所有第10章：所有第17章：所有
形式语言和自动机理论的经典表述考察了文法和乔姆斯基体系中抽象机之间的关系。本书同时也描述了确定型有限自动机、下推自动机、线性无界自动机和图灵机的可计算性性质。抽象机的计算能力的分析，是通过使用图灵机和无限制文法产生的语言，来识别语言的等价性而建立的。
可计算性理论考察了算法问题解决的能力和局限。可计算性包括确定性和丘吉尔—图灵理论。其中，后者通过建立图灵可计算性和μ-递归函数的等价性而获得支持。对角化证明用来证明图灵机的停机问题是无解的，而问题化简则用来构造有关算法计算的一系列问题的不确定性。
对于计算复杂性的研究，我们首先考虑计算所需要的资源的度量方法。我们选取图灵机作为评估复杂性的框架，时间和空间的复杂性是通过图灵机计算中使用的转换数量和内存数量来计算的。类问题可以使用确定型图灵机在多项式时间内解决，这类问题被认为是具有有效算法解决方案的一类问题。在这之后，类问题和NP完全理论也会给与介绍。逼近算法用来获得NP完全优化问题的近似最优解。
形式化语言理论在计算科学中最重要的应用是使用文法来指定编程语言的语法。这门课程强调使用形式化技术来定义编程语言和提出有效的分解策略，它起始于用来生成语言的上下文无关文法和用于识别模式的有限自动机的介绍。介绍语言的定义之后，第18章至第20章考察了LL和LR文法以及通过这些类型的文法定义的语言的确定性分解的性质。
练习
掌握计算科学的理论基础的过程不是一场只需旁观的体育运动会。一个人只有通过解决问题，并考察主要结论的证明，才能够充分理解理论的概念、算法和精妙之处的。也就是说，对整体理解需要更多的细微努力。为了达到这一目的，我们在每章后面都编写了一些练习。这些练习包括很多方面，既有本章介绍的主题的构造练习，也有对理论的扩展。
每部分的练习中都有几个是带星号的，这些问题要比本章的其他问题更难，在本质上更理论些，或者更特别和有趣。
符号
计算科学理论是有效性计算的能力和缺陷的数学检查。与其他形式化分析类似，这种表示必须能够提供概念、结构和操作的精确且无二义性的定义。下面的表示法将贯穿本书。

条　　目描　　述例　　子元素和字符串字符是字母表中的小写斜体字母a，b，abc函数小写斜体字母f，g，h集合和关系大写字母X，Y，Z，∑，Г 文法大写字母G，G1，G2文法的变量大写斜体字母A，B，C，S抽象机大写字母M，M1，M2
使用罗马字母表示集合和数学结构在一定程度上不太标准，然而这样做能使得一种结构的构成成分很容易地被识别出来。例如，上下文无关文法的结构是G=（∑，V，P，S）。仅仅从字体上我们就可以看出，G包含三个集合和变量S。
整本书使用三种计数系统，每章、节、条目都给出一条引用。一个计数序列记录了定义、引理、定理、推论和算法；另一个序列用来识别例子；图、表以及练习使用章节序号来标识。
证明的结尾以■标记结束，例子的结尾以□标记结束。符号索引，包括这些符号的介绍，以及它们出现的页数　指英文原书的页码，而非本书页码。——编辑注都在附录Ⅰ中给出。
补充
我们给出的部分练习的解答，仅仅是为了辅助教师授课　需要练习解答的教师请按书后的教师服务沟通表中列出的联系方式联系培生教育出版集团北京代表处。
——编辑注。
声明
首先，我要感谢我的妻子Janice和女儿Elizabeth。由于她们的善良、耐心和顾全大局，才使我能成功地完成本书。我还要感谢the Institut de Recherche en Informatique de Toulouse的同事和朋友。这本书修订的第一稿是在2004年我访问IRIT期间完成的。特别要感谢Didier Dubois和Henri Prade的慷慨和好客。
每一版我都会多感谢一些对本书作出贡献的人，恳切感谢所有使用这本书的学生和教师，以及那些提出批评、校勘、修改与建议，从而促进我完善本书的人。其中很多意见我已经加入到这一版中。谢谢你们花费时间把意见发给我，希望你们以后会仍然如此。我的信箱是tsudkamp@cs.wright.edu。
这本书的不同版本曾经得到许多计算机专家的评论，其中包括下面这些教授：Andrew Astromoff（San Francisco State University），Dan Cooke（University of Texas-EI Paso），Thomas Fernandez，Sandeep Gupta（Arizona State University），Raymond Gumb（University of Massachusetts-Lowell），Thomas F.Hain（University of South Alabama），Michael Harrison（University of California at Berkeley），David Hemmendinger（Union College），Steve Homer（Boston University），Dan Jurca（California State University-Hayward），Klaus Kaiser（University of Houston），C.Kim（University of Oklahoma），D.T.Lee（Northwestern University），Karen Lemone（Worcester Polytechnic Institute），C.L.Liu（University of Illinois at Urbana-Champaign），Richard J.Lorentz（California State University-Northridge），Fletcher R.Norris（The University of North Carolina at Wilmington），Jeffery Shallit（University of Waterloo），Frank Stomp（Wayne State University），William Ward（University of South Alabama），Dan Ventura（Brigham Young University），Charles Wallace（Michigan Technological University），Kenneth Williams（Western Michigan University）和Hsu-Chun Yen（Iowa State University），在此感谢你们。
我还要感谢Addison-Wesley出版公司计算机科学教育分公司和Windfall Software中参与这个项目的小组成员的帮助。

Thomas A.Sudkamp
Dayton，Ohio

Thomas A.Sudkamp：Thomas A.Sudkamp: 是美国莱特州立大学计算机科学及工程系的教授，他的研究领域广泛，包括近似推理、人工智能、数理逻辑、建模软计算的应用、复杂问题领域的决策制定以及不确定、不精确信息和知识发掘的机器学习。Sudkamp教授目前还担任IEEE Transactions on System, Man, and Cybernetics和IEEE Transactions on Fuzzy Systems的副编辑，International Journal of Approximate Reasoning和Fuzzy Sets and Systems的领域编辑。他也曾经担任过北美模糊信息处理协会（NAFIPS）的主席以及国际模糊系统联盟（IFSA）的副主席。

孙家骕：北京大学软件学院教学指导委员会成员。北京大学信息科学技术学院计算机系教授、博士生导师。主要研究方向：计算机语言，程序理解，软件逆向工程、再工程。主持、参加过多项国家科研项目；发表论文30余篇；编写教材10余部。曾获北京大学优秀教学奖、机电部“七五”攻关荣誉证书。

理论计算机科学是推动计算机技术和应用向前发展的巨大动力。形式语言、自动机、可计算性、计算复杂性以及相关内容构成的计算理论，是理论计算机科学的基础内容之一。学习、研究这些内容，不仅为进一步学习、研究理论计算机科学打下基础，而且对增强形式化能力和推理能力也有帮助作用，这些能力对从事计算机技术中的形式化方法、技术等研究，是不可缺少的。
　　本书是由美国莱特州立大学计算机科学及工程系的Thomas A.Sudkamp教授编写的高等学校教材，主要介绍形式语言、自动机、可计算性、计算复杂性和上下文无关语言的确定性分析等内容。本书不仅介绍了计算机科学的基础，而且通过概念的严格表述，以及使用通俗的例子来阐释定理，从而期望能够帮助学生提高数学论证能力以及对计算理论知识的全面深入的理解。书中每章后面都有大量习题，通过完成这些习题，学生可以加深对本章内容的理解。本书是理论计算机科学的优秀教材之一。
　　本书可以用作计算机科学、计算机工程及其相关专业的教材，也可以作为从事计算理论、形式语言以及计算机系统研发的研究人员和工程技术人员的参考书。
引进国外的优秀计算机教材，对我国的计算机教育事业的发展会起到积极的推动作用，也是与世界接轨、建立世界一流大学不可缺少的条件之一。我们把本书介绍给国内从事计算机教育事业的同行们，以供参考。
　　参加本书翻译的有：孙家骕同志，负责各章译稿的详细修改和全书的统稿；郝丹同志负责第1到第4章及前言的翻译；刘江红同志负责第5到第7章的翻译；程邵斌同志负责第8到第10章的翻译；李琰同志负责第11到第13章的翻译；侯姗姗同志负责第14到第17章的翻译；黄晓晨同志负责第18到第20章及附录的翻译。
由于我们的能力有限，难免有不当之处，敬请读者不吝赐教。

　　译　者
　　2007年4月

目　　录
出版者的话
专家指导委员会
译者序
前言
绪论

第一部分　基　础

第1章　数学预备知识　2
　1.1　集合论　2
　1.2　笛卡儿积、关系和函数　4
　1.3　等价关系　6
　1.4　可数集合和不可数集合　7
　1.5　对角化和自反　9
　1.6　递归定义　11
　1.7　数学归纳　13
　1.8　有向图　15
　1.9　练习　18
　参考文献注释　20
第2章　语言　21
　2.1　字符串和语言　21
　2.2　语言的有穷规格说明　23
　2.3　正则集合和表达式　25
　2.4　正则表达式和文本搜索　28
　2.5　练习　30
　参考文献注释　32

第二部分　文法、自动机和语言

第3章　上下文无关文法　34
　3.1　上下文无关文法和语言　36
　3.2　文法和语言的例子　41
　3.3　正则文法　44
　3.4　验证文法　45
　3.5　最左推导和二义性　48
　3.6　上下文无关文法和编程语言定义　51
　3.7　练习　53
　参考文献注释　56
第4章　上下文无关文法范式　57
　4.1　文法转换　57
　4.2　消去λ规则　58
　4.3　去掉链规则　62
　4.4　无用符　64
　4.5　乔姆斯基范式　67
　4.6　CYK算法　69
　4.7　去掉直接左递归　71
　4.8　格立巴赫范式　73
　4.9　练习　77
　参考文献注释　80
第5章　有限自动机　81
　5.1　一个有限状态自动机　81
　5.2　确定型有限自动机　82
　5.3　状态图和例子　84
　5.4　非确定型有限自动机　88
　5.5　λ-转换　91
　5.6　去掉非确定性　94
　5.7　DFA的最小化　99
　5.8　练习　103
　参考文献注释　107
第6章　正则语言的性质　108
　6.1　有限状态机接收正则语言　108
　6.2　表达式图　109
　6.3　正则文法和有限自动机　111
　6.4　正则语言的封闭性质　114
　6.5　非正则语言　115
　6.6　规则语言的泵引理　116
　6.7　Myhill-Nerode定理　119
　6.8　练习　122
　参考文献注释　125
第7章　下推自动机和上下文无关
语言　126
　7.1　下推自动机　126
　7.2　PDA的变种　129
　7.3　上下文无关语言的接收　132
　7.4　上下文无关语言的泵引理　136
　7.5　上下文无关语言的封闭性　138
　7.6　练习　140
　参考文献注释　143

第三部分　可 计 算 性

第8章　图灵机　146
　8.1　标准图灵机　146
　8.2　作为语言接收器的图灵机　148
　8.3　可供选择接收标准　150
　8.4　多道图灵机　151
　8.5　双向图灵机　151
　8.6　多带图灵机　153
　8.7　非确定型图灵机　157
　8.8　用来枚举语言的图灵机　162
　8.9　练习　166
　参考文献注释　169
第9章　图灵可计算函数　170
　9.1　函数的计算　170
　9.2　数值计算　172
　9.3　图灵机的顺序操作　174
　9.4　函数的合成　178
　9.5　不可计算函数　180
　9.6　关于编程语言　181
　9.7　练习　184
　参考文献注释　186
第10章　乔姆斯基层次　187
　10.1　无限制文法　187
　10.2　上下文有关文法　191
　10.3　线性有界自动机　192
　10.4　乔姆斯基层次　195
　10.5　练习　195
　参考文献注释　197
第11章　判定问题与丘奇—图灵
论题　198
　11.1　判定问题的描述　198
　11.2　判定问题和递归语言　199
　11.3　问题归约　201
　11.4　丘奇—图灵论题　203
　11.5　通用机　204
　11.6　练习　207
　参考文献注释　208
第12章　不可判定性　209
　12.1　图灵机的停机问题　209
　12.2　问题归约和不可判定性　211
　12.3　其他的停机问题　213
　12.4　莱斯定理　215
　12.5　不可解决的词问题　216
　12.6　波斯特对应问题　218
　12.7　上下文无关文法中的不可判定
问题　221
　12.8　练习　223
　参考文献注释　225
第13章　Mu-递归函数　226
　13.1　原始递归函数　226
　13.2　一些原始递归函数　228
　13.3　有界操作符　230
　13.4　除法函数　234
　13.5　歌德尔数字和串值递归　235
　13.6　可计算部分函数　237
　13.7　图灵可计算函数和Mu-递归函数　240
　13.8　修订的丘奇—图灵论题　243
　13.9　练习　245
　参考文献注释　249

第四部分　计算复杂性

第14章　时间复杂性　252
　14.1　复杂性度量　252
　14.2　增长的速度　253
　14.3　图灵机的时间复杂性　256
　14.4　复杂性和图灵机的变种　259
　14.5　线性加速　260
　14.6　语言时间复杂性的属性　262
　14.7　计算机计算的模拟　266
　14.8　练习　268
　参考文献注释　270
第15章　、　和库克定理　271
　15.1　非确定型图灵机的时间复杂性　271
　15.2　类和类　272
　15.3　问题表示和复杂性　273
　15.4　判定问题和复杂性类　275
　15.5　哈密尔顿回路问题　276
　15.6　多项式时间归约　278
　15.7　=？　279
　15.8　可满足性问题　280
　15.9　复杂类的关系　287
　15.10　练习　287
　参考文献注释　289
第16章　NP-完全问题　290
　16.1　归约和NP-完全问题　290
　16.2　三元可满足性问题　291
　16.3　三元可满足性的归约　292
　16.4　归约和子问题　299
　16.5　最优化问题　302
　16.6　近似算法　303
　16.7　近似方案　305
　16.8　练习　307
　参考文献注释　308
第17章　其他复杂性类　309
　17.1　派生的复杂性类　309
　17.2　空间复杂性　310
　17.3　空间复杂性和时间复杂性的关系　312
　17.4　-空间，-空间和萨维奇
定理　315
　17.5　-空间完全性　318
　17.6　一个难解问题　320
　17.7　练习　321
　参考文献注释　321

第五部分　确定型语法分析

第18章　语法分析引论　324
　18.1　文法图　324
　18.2　自顶向下语法分析　325
　18.3　归约和自底向上语法分析　328
　18.4　自底向上语法分析器　329
　18.5　语法分析和编译　331　18.6　练习　332
　参考文献注释　333
第19章　LL(k)文法　334
　19.1　上下文无关文法中的预读　334
　19.2　FIRST集合、FOLLOW集合和预读
集合　336
　19.3　强LL(k)语法　338
　19.4　FIRSTk集合的构造　339
　19.5　FOLLOWk集合的构造　341
　19.6　强LL(1)文法　342
　19.7　强LL(k)分析器　344
　19.8　LL(k)文法　345
　19.9　练习　346
　参考文献注释　348
第20章　LR(k)文法　349
　20.1　LR(0)上下文　349
　20.2　LR(0)分析器　351
　20.3　LR(0)机　352
　20.4　被LR(0)机接收　356
　20.5　LR(1)文法　360
　20.6　练习　365
　参考文献注释　366
附录Ⅰ　标记索引　367

附录Ⅱ　希腊字母表　370

附录Ⅲ　ASCⅡ字符集　371

附录Ⅳ　Java的BNF范式定义　372

参考文献　379

索引　384