本书是理论计算机科学方面的优秀教材，主要介绍形式语言、自动机、可计算性和相关内容。本书特别注意定义、定理的准确性和严格性，在定理的证明中给出了直观的动机和框架，避免多余的数学细节，这有利于培养学生形式化和严格的数学推理能力，加强对问题的理解；本书通过精心设计的大量示例，生动剖析了各种定理和定义，概念清晰，深入浅出。每章后面还给出了难度不同的习题，并给出部分习题的解答，可使学生加深对基本原理的理解并增强应用能力。

本书主要介绍形式语言、自动机、可计算性和相关内容。主要内容包括：计算理论导引、有穷自动机、正则语言与正则文法、上下文无关语言及文法、下推自动机、图灵机、形式语言和自动机的层次结构、计算复杂性等。每节后面都给出了习题，并包含部分习题的解答，方便教学。

本书是理论计算机科学方面的优秀教材之一，可作为高等院校计算机专业的教材，也可作为计算机系统研发人员的参考书。

出版者的话

专家指导委员会

译者序

前言

第1章 计算理论导引 1

 1.1数学预备知识和表示 2

1.1.1集合 2

1.1.2函数和关系 3

1.1.3图和树 5

1.1.4证明方法 7

 1.2三个基本概念 l0

1.2.1语言 11

1.2.2文法 13

1.2.3自动机 l8

 1.3一些应用 2l

第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确定型有穷接受器和非确定型有穷接受器的等价性 4O

 2.4减少有穷自动机中状态的化简 45

第3章 正则语言与正则文法 5l

 3.1正则表达式 5l

3.1.1正则表达式的形式化定义 5l

3.1.2和正则表达式相关的语言 5l

 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简单集合运算的封闭性 7O

4.1.2其他运算的封闭性 7l

 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消除九产生式 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波斯特对应问题 2l3

 12.4上下文无关语言的不可判定问题 2l8

第13章 其他的计算模型 223

 13.1递归函数 224

13.1.1原始递归函数 225

13.1.2 Ackermann函数 227

13.1.3递归函数 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