本书是理论计算机科学方面的优秀教材，主要介绍形式语言、自动机、可计算性和相关内容。本书特别注意定义、定理的准确性和严格性，在定理的证明中给出了直观的动机和框架，避免多余的数学细节，这有利于培养学生形式化和严格的数学推理能力，加强对问题的理解；本书通过精心设计的大量示例，生动剖析了各种定理和定义，概念清晰，深入浅出。每章后面还给出了难度不同的习题，并给出部分习题的解答，可使学生加深对基本原理的理解并增强应用能力。
无
本书主要介绍形式语言、自动机和可计算性等相关内容。这些内容形成计算理论的主体。这方面的课程现在是计算机科学课程体系中必有的一部分，并且这门课程通常开设在计算机课程的早期。因此，这本书面向的读者主要包括计算机科学系或计算机工程系大学二年级和三年级的学生。
学习本书的预备知识包括了解某种高级程序设计语言（通常包括C、C++或Java），熟悉数据结构和算法的基础知识。另一个预备课程是离散数学，包括集合论、函数、关系、逻辑和数学推理的基础。这门课程也是标准的计算机科学导论课程的一部分。
计算理论的研究有几个目的，其中最为重要的目的包括：（1）使学生熟悉计算机科学的基础和原则，（2）为后续课程做准备，（3）增强学生进行规范和严格数学推理的能力。尽管我在这本书中采用的表达方式主要是为了达到前两个目的，但是我认为这本书也达到了第三个目的。为了表达得更加清晰，使得读者能够认识事物的本质，本书强调直觉上的动机，并通过例子阐述这些想法。只要可以选择，我就会选择那些容易掌握的论据，而不是那些简洁、优雅，可是在概念上却难以理解的论据。我在这本书中准确地声明定义和定理，给出证明的动机，不过省略了程序和冗长的细节。这样做是出于教育学的考虑。许多证明是归纳或反证的一般应用，它们对于不同的特殊问题而言也不同。这样的详细论证不仅是不必要的，而且会影响到整体的流畅性。因此，我们略过很多论证的细节，可能会有人出于完整性的考虑而质疑这种做法，我本人并不认为这是一个缺陷。数学技巧无法通过阅读别人的论证过程而培养出来，而应该是考虑问题的本质，发现能够证明论点的想法，然后通过精确的细节实现它。这后一种技巧是必学的。我认为这本书的论证框架提供了一个这样实践的正确起点。
从事计算机科学研究的学生有时把计算理论方面的课程视为非必需的，且认为它缺乏实践意义。为了说服他们，我们需要吸引他们的兴趣和精力，比如处理难解问题的坚韧性和创造性。为此，我的方法强调通过解决问题来学习。
使用这种解决问题的学习方法，我想让学生主要通过按问题分类的示例来学习知识。正如它们同定理和定义之间的关联性一样，这种例子通过隐藏其后的概念可以显现其动机。同时，这些例子还有其不平凡的一面，它们有助于学生发现解决方案。在这种方法中，课后习题更有助于学习过程。每个章节后面的习题阐明和解释了本章的内容，在不同的层次上调动学生解决问题的能力。其中一些习题相当简单，挑选了一些书中没有完成讨论的内容让学生继续进行思考。另一些习题非常难，即使对比较聪明的学生也是一种挑战。这两种习题的适当结合会成为非常有效的教学手段。学生不必解决所有的问题，但是应该根据课程和教师的要求完成部分习题。不同的学校开设的计算机科学课程不同，有的强调理论方面，有的几乎完全面向实际应用。倘若课程选择考虑到了学生的背景和兴趣，那么我相信这本书可以用于上述任何学校。同时，教师需要告诉学生他们期望学生能够做到的抽象程度。对于面向论证的习题更是如此。当我说“证明”或“表明”时，我认为学生可以构造出一个论证过程，然后产生一个清晰的结论。一个论证过程要形式化到什么程度由教师决定，而且这种指导应该在课程的早期给出。
这本书的内容适合在一学期内完成。教师可以讲授这本书的大部分内容，不过，重点就由教师自己决定了。尽管这本书中证明不多，不过我在我的班级里通常都是简略地讲述这些证明。我通常只给出足够的讲解，使结论可信，然后让学生独自去阅读剩下的部分。总的来说，如果不想以后碰到困难，还是尽可能不要跳过某些章节。标有星号的章节可以略过，略过这部分内容不会影响你读后面的内容。尽管如此，大部分的内容还是必需的，而且不能够跳过。
这本书的第1版出版于1990年，第2版出版于1996年。对新版本的需求是令人高兴的，这表明我的这种通过语言而不是计算的教学方法是可行的。第2版相对于第1版的变化不是彻底的变化，而是在原有基础上的改进。它修改了第1版中晦涩和错误的内容。无论如何，第2版看起来已经相对稳定，需要进行修改的地方也很少。所以，第3版的大部分内容和第2版差不多。第3版主要的新特点是增加了一些带解答的习题。
最初，我并不愿意给出习题的解答，因为这样就会减少可以用来作为课后练习的习题数量。然而，几年来，我收到来自世界各地学生的求助请求，因此我决定在这一版中给出一部分习题的解答。我又增加了一些新的习题从而保证没有解答的习题的数量。我只挑选那些有重要指导意义的习题来给出解答。因此，我没有仅仅给出最终的答案，而是给出最终结果的推理依据。许多习题使用了同样的原理，我通常从中选择具有代表性的习题给出解答，希望学生能够举一反三。我相信挑选出来的这部分习题的解答可以帮助学生提高他们解决问题的能力，并且保留一部分比较好的习题给教师作为课后作业使用。在本书中，有解答和提示的习题都标有。
此外，为响应读者的建议，我把一些比较难的习题做了标注。这样做不太容易，毕竟习题跨越的难度范围很大，而且同样一道习题对于某个学生而言简单，另一个学生可能就会认为很难。但是仍然存在一部分的习题，它们对于我的大多数学生而言都是有挑战性的。这部分的习题我用一个星号（★）标明。当然还存在一些特殊的习题，它们没有明确的答案。要想解决它们，可能需要思索，阅读一些附加内容，或者需要一些计算机编程。虽然它们不适合作为常规的作业来布置，但是它们可以作为进一步学习的切入点。这种习题我标了双星号（★★）。
在过去的10年里，我得到了很多评论家、教师和学生的有益建议。这样的人太多，我在这里无法一一列举他们的名字。我衷心感谢他们对我的帮助。他们的反馈对于我改进这本书而言是极其宝贵的。
Peter Linz
Peter Linz：Peter Linz: Peter Linz 加利福尼亚大学戴维斯分校计算机科学系的荣誉教授，研究重点是：开发数值分析理论，以构建可靠的数值方法并将其用于科学计算中的问题求解环境的设计。Linz教授的相关著作还有 Exploring Numerical Methods: An Introduction to Scientific Computing。
孙家骕 等：孙家骕: 北京大学软件学院教学指导委员会成员。北京大学信息科学技术学院计算机系教授、博士生导师。主要研究方向：计算机语言，程序理解，软件逆向工程、再工程。主持、参加过多项国家科研项目；发表论文30余篇；编写教材10余部。曾获北京大学优秀教学奖、机电部“七五”攻关荣誉证书。
理论计算机科学是推动计算机技术向前发展的强大动力。形式语言、自动机、可计算性和相关方面内容构成的计算理论，是理论计算机科学的基础内容之一。学习、研究这些内容，不仅为进一步学习、研究理论计算机科学所必需，而且对增强形式化能力和推理能力有重要作用，这些能力对从事计算机技术中的软件形式化等研究，是不可缺少的。
本书是由美国加利福尼亚大学戴维斯分校的Peter Linz教授编写的高等学校教材，主要介绍形式语言、自动机、可计算性和相关内容。本书特别注意定义、定理的准确性和严格性，这有利于培养学生形式化和严格的数学推理的能力；本书强调讲述问题、定理时的直觉性，这有利于学生对问题的理解；本书在定理的证明中往往只给出框架，而略去细节，这有利于学生进一步思考，加强对问题的理解；本书在每节后面都给出了习题，对部分习题还给出了解答，这有利于学生通过做习题加深对基本原理的理解并增强应用能力。本书是理论计算机科学的优秀教材之一。
本书可以用作计算机理论专业和计算机工程专业的教材，也可以作为计算机系统研发人员的参考书。
引进国外的优秀计算机教材，无疑会对我国的计算机教育事业的发展起积极的推动作用，也是与世界接轨、建立世界一流大学不可缺少的条件。我们把本书介绍给国内从事计算机教育事业的同行们，以供参考。
本书第1版于1990年发行，这个译本是我们根据它的第3版翻译的。参加本书翻译的有：孙家同志负责各章译稿的详细修改和全书的统稿；郝丹同志负责第1章到第5章的翻译；罗景同志负责第6章到第9章的翻译；李炎同志负责第11章到第14章的翻译；孙宏涛同志负责第10章、习题解答及索引的翻译。
由于我们的能力有限，译文中难免有不当之处，敬请读者不吝赐教。
译 者
2005年6月
第1章 计算理论导引 1
1.1 数学预备知识和表示 2
1.1.1 集合 2
1.1.2 函数和关系 3
1.1.3 图和树 5
1.1.4 证明方法 7
1.2 三个基本概念 10
1.2.1 语言 11
1.2.2 文法 13
1.2.3 自动机 18
1.3 一些应用* 21
第2章 有穷自动机 27
2.1 确定型有穷接受器 27
2.1.1 确定型接受器和转换图 27
2.1.2 语言和dfa对应的语言 29
2.1.3 正则语言 32
2.2 非确定型有穷接受器 35
2.2.1 非确定型接受器的定义 35
2.2.2 为什么需要非确定型 38
2.3 确定型有穷接受器和非确定型有穷接受器的等价性 40
2.4 减少有穷自动机中状态的化简* 45
第3章 正则语言与正则文法 51
3.1 正则表达式 51
3.1.1 正则表达式的形式化定义 51
3.1.2 和正则表达式相关的语言 51
3.2 正则表达式和正则语言之间的联系 55
3.2.1 正则表达式表示正则语言 55
3.2.2 正则语言的正则表达式 56
3.2.3 描述简单模式的正则表达式 59
3.3 正则文法 62
3.3.1 右线性文法和左线性文法 62
3.3.2 右线性文法生成正则语言 63
3.3.3 正则语言的右线性文法 64
3.3.4 正则语言和正则文法的等价性 66
第4章 正则语言的性质 69
4.1 正则语言的封闭性质 69
4.1.1 简单集合运算的封闭性 70
4.1.2 其他运算的封闭性 71
4.2 正则语言的基本问题 77
4.3 识别非正则语言 78
4.3.1 使用鸽巢原理 79
4.3.2 泵引理 79
第5章 上下文无关语言 85
5.1 上下文无关文法 85
5.1.1 上下文无关语言的例子 86
5.1.2 最左推导和最右推导 87
5.1.3 推导树 88
5.1.4 句型和推导树之间的关系 89
5.2 分析和二义性 92
5.2.1 分析和成员资格判定 92
5.2.2 文法和语言的二义性 95
5.3 上下文无关文法和程序设计语言 99
第6章 上下文无关文法的化简与范式 101
6.1 文法变换方法 101
6.1.1 一个有用的代入规则 101
6.1.2 删除无用产生式 103
6.1.3 消除l产生式 106
6.1.4 消除单位产生式 107
6.2 两个重要的范式 111
6.2.1 乔姆斯基范式 112
6.2.2 格里巴克范式 114
6.3 上下文无关文法的成员资格判定算法* 116
第7章 下推自动机 119
7.1 非确定型下推自动机 119
7.1.1 下推自动机的定义 120
7.1.2 下推自动机接受的语言 121
7.2 下推自动机与上下文无关语言 125
7.2.1 上下文无关语言相应的下推自动机 125
7.2.2 下推自动机相应的上下文无关文法 129
7.3 确定型下推自动机和确定型上下文无关语言 133
7.4 确定型上下文无关语言的文法* 136
第8章 上下文无关语言的性质 141
8.1 两个泵引理 141
8.1.1 上下文无关语言的泵引理 141
8.1.2 线性语言的泵引理 144
8.2 上下文无关语言的封闭性质和判定算法 146
8.2.1 上下文无关语言的封闭性质 146
8.2.2 上下文无关语言的可判定性质 149
第9章 图灵机 153
9.1 标准图灵机 153
9.1.1 图灵机的定义 153
9.1.2 作为语言接受器的图灵机 157
9.1.3 作为转换器的图灵机 160
9.2 完成复杂任务的组合图灵机 164
9.3 图灵论题 168
第10章 图灵机的其他模型 171
10.1 对图灵机的较小修改 171
10.1.1 自动机类的等价性 171
10.1.2 带不动选择的图灵机 172
10.1.3 单向无穷带图灵机 174
10.1.4 离线图灵机 175
10.2 具有更复杂存储的图灵机 177
10.2.1 多带图灵机 177
10.2.2 多维图灵机 179
10.3 非确定型图灵机 181
10.4 通用图灵机 183
10.5 线性有界自动机 186
第11章 形式语言和自动机的层次结构 189
11.1 递归语言和递归可枚举语言 189
11.1.1 非递归可枚举的语言 190
11.1.2 非递归可枚举语言 191
11.1.3 递归可枚举但非递归的语言 192
11.2 无限制文法 193
11.3 上下文相关文法和语言 198
11.3.1 上下文相关语言和线性有界自动机 198
11.3.2 递归语言和上下文相关语言的关系 199
11.4 乔姆斯基层次结构 201
第12章 算法计算的限制 205
12.1 图灵机所不能解决的问题 205
12.1.1 可计算性和可判定性 205
12.1.2 图灵机停机问题 206
12.1.3 将一个不可判定问题简化成另外一个问题 208
12.2 递归可枚举语言的不可判定问题 211
12.3 波斯特对应问题 213
12.4 上下文无关语言的不可判定问题 218
第13章 其他的计算模型 223
13.1 递归函数 224
13.1.1 原始递归函数 225
13.1.2 Ackermann函数 227
13.1.3 m递归函数 228
13.2 波斯特系统 229
13.3 重写系统 232
13.3.1 矩阵文法 232
13.3.2 马尔科夫算法 233
13.3.3 L系统 234
第14章 计算复杂性介绍 237
14.1 计算的效率 237
14.2 图灵机和复杂性 239
14.3 语言族和复杂性类 241
14.4 复杂性类P和NP 243
部分习题的解答和提示 247
参考文献 283
索引 285
