目录
译者序
前言
理论部分
第 1 章 计算理论概论　　　　　　 2
1.1 数学预备知识和符号表示　　　 3
1.1.1 集合　　　　　　　　　3
1.1.2 函数和关系　　　　　　　5
1.1.3 图和树　　　　　　　 8
1.1.4 证明方法　　　　　　　 9
1.2 三个基本概念　　　　　　　15
1.2.1 语言　　　　　　　　　15
1.2.2 文法　　　　　　　　 19
1.2.3 自动机　　　　　　　 24
1.3 应用 *　　　　　　　　 27
第 2 章 有穷自动机　　　　　　　 33
2.1 确定的有穷接受器　　　　　 33
2.1.1 确定的接受器和转移图　　 34
2.1.2 语言和 DFA 的语言　　　　36
2.1.3 正则语言　　　　　　 40
2.2 非确定的有穷接受器　　　　 44
2.2.1 非确定的接受器的定义　　 44
2.2.2 为什么需要非确定性？　　 48
2.3 确定与非确定的有穷接受器的
等价性　　　　　　　　 51
2.4 减少有穷自动机中状态的
化简 *　　　　　　　　 58
第 3 章 正则语言和正则文法　　　　 64
3.1 正则表达式.　　　　　　　64
3.1.1 正则表达式的形式定义　　 64
3.1.2 正则表达式所关联的语言　　 65
3.2 正则表达式和正则语言的
联系　　　　　　　　　　70
3.2.1 正则表达式表示正则语言　　 70
3.2.2 正则语言的正则表达式　　 72
3.2.3 描述简单模式的正则表达式　 77
3.3 正则文法　　　　　　　　 80
3.3.1 左线性文法和右线性文法　　 80
3.3.2 右线性文法生成正则语言　　 81
3.3.3 正则语言的右线性文法　　 83
3.3.4 正则语言和正则文法的
等价性　　　　　　　　 85
第 4 章 正则语言的性质　　　　　 89
4.1 正则语言的封闭性　　　　　 90
4.1.1 简单集合运算的封闭性　　 90
4.1.2 其他运算的封闭性　　　　 92
4.2 正则语言的基本问题　　　　 99
4.3 识别非正则语言　　　　　　102
4.3.1 鸽巢原理的使用　　　　　102
4.3.2 泵引理　　　　　　 103
第 5 章 上下文无关语言　　　　　　113
5.1 上下文无关文法　　　　　　114
5.1.1 上下文无关文法示例　　　 114
5.1.2 最左推导和最右推导　　　 116
5.1.3 推导树　　　　　　 117
5.1.4 句型和推导树的关系　　　 119
5.2 解析和歧义性　　　　　　 123
5.2.1 解析和成员资格　　　　　123
5.2.2 文法和语言的歧义性　　　 127
5.3 上下文无关文法和程序设计
语言　　　　　　　　　 132
第 6 章 上下文无关文法的化简和
范式　　　　　　　　　　135
6.1 文法转换的方法　　　　　　136
6.1.1 有用的代入规则　　　　　136
6.1.2 消除无用的产生式　　　 138
6.1.3 消除 λ-产生式　　　　 141
6.1.4 消除单元产生式　　　　　143
6.2 两种重要的范式　　　　　　149
6.2.1 乔姆斯基范式　　　　　150
6.2.2 格雷巴赫范式　　　　　152
6.3 上下文无关文法的成员资格
判定算法 *　　　　　　　 156
第 7 章 下推自动机　　　　　　 159
7.1 非确定的下推自动机　　　 160
7.1.1 下推自动机的定义　　　 160
7.1.2 下推自动机接受的语言　　　163
7.2 下推自动机和上下文无关
语言　　　　　　　　　 168
7.2.1 上下文无关语言对应的下推
自动机　　　　　　 168
7.2.2 下推自动机对应的上
下文无关文法　　　　　　173
7.3 确定的下推自动机和确定的
上下文无关语言　　　　　　179
7.4 确定的上下文无关语言的
文法 *　　　　　　　　　184
第 8 章 上下文无关语言的性质　　　 188
8.1 两个泵引理　　　　　　 188
8.1.1 上下文无关语言的泵引理　 189
8.1.2 线性语言的泵引理　　　 192
8.2 上下文无关语言的封闭性
和判定算法　　　　　　 196
8.2.1 上下文无关语言的封闭性　 197
8.2.2 上下文无关语言的一些可判
定性质　　　　　　 200
第 9 章 图灵机　　　　　　　　　204
9.1 标准的图灵机　　　　　　 204
9.1.1 图灵机的定义　　　　　205
9.1.2 作为语言接受器的图灵机　 209
9.1.3 作为转换器的图灵机　　　 212
9.2 完成复杂任务的组合图灵机　218
9.3 图灵论题　　　　　　　　　222
第 10 章 图灵机的其他模型　　　　 225
10.1 对图灵机的小改动　　　　 225
10.1.1 自动机类的等价性　　　　226
10.1.2 可驻停图灵机　　　　226
10.1.3 半无穷带图灵机　　　　 228
10.1.4 离线图灵机　　　　　　 229
10.2 具有更复杂存储的图灵机　　232
10.2.1 多带图灵机　　　　　　 232
10.2.2 多维图灵机　　　　　　 234
10.3 非确定的图灵机　　　　　 236
10.4 通用图灵机　　　　　　　238
10.5 线性界限自动机　　　　　 242
第 11 章 形式语言和自动机的层次
结构　　　　　　　　 245
11.1 递归语言和递归可枚举
语言　　　　　　　　 245
11.1.1 非递归可枚举语言　　　　247
11.1.2 一个非递归可枚举的语言　 248
11.1.3 一个递归可枚举但非递归
的语言　　　　　　　 249
11.2 无限制文法　　　　　　　251
11.3 上下文有关文法和语言　　 256
11.3.1 上下文有关语言和线性界
限自动机　　　　　　257
11.3.2 递归语言和上下文有关语言
的关系　　　　　　　 258
11.4 乔姆斯基层次结构　　　　 261
第 12 章 算法计算的限制　　　　 264
12.1 图灵机无法解决的问题　　 264
12.1.1 可计算性和可判定性　　 265
12.1.2 图灵机停机问题　　　　 265
12.1.3 不可判定问题的归约　　 268
12.2 递归可枚举语言的不可判定
问题　　　　　　　　 271
12.3 波斯特对应问题　　　　　 274
12.4 上下文无关语言的不可判定
问题　　　　　　　　 279
12.5 关于效率的问题　　　　　 282
第 13 章 其他计算模型　　　　　　　284
13.1 递归函数　　　　　　　　285
13.1.1 原始递归函数　　　　286
13.1.2 阿克曼函数　　　　　　289
13.1.3 μ-递归函数　　　　　　290
13.2 波斯特系统　　　　　　　292
13.3 重写系统　　　　　　　　295
13.3.1 矩阵文法　　　　　　296
13.3.2 马尔可夫算法　　　　297
13.3.3 L-系统　　　　　　　　298
第 14 章 计算复杂性概述　　　　 300
14.1 计算的效率　　　　　　　300
14.2 图灵机模型和复杂性　　　　302
14.3 语言族和复杂性类　　　　 305
14.4 复杂性类 P 和 NP　　　　 308
14.5 几个 NP 问题　　　　　 309
14.6 多项式时间归约　　　　　 312
14.7 NP 完全性和一个未解决的
问题　　　　　　　　 314
应用部分
第 15 章 编译器和解析　　　　　　　318
15.1 编译器　　　　　　　　 318
15.2 自顶向下和自底向上的
解析　　　　　　　　 326
15.3 FIRST 函数　　　　　　 330
15.4 FOLLOW 函数　　　　　 337
第 16 章 LL 解析　　　　　　　　343
16.1 上下文无关文法转换为
NPDA　　　　　　　　 344
16.1.1 LL 解析的下推自动机　　　 344
16.1.2 LL 解析中将上下文无关文
法转换为 NPDA 的算法　344
16.2 LL(1) 分析表　　　　　 348
16.3 LL(1) 解析算法　　　　　 350
16.4 LL(k) 解析　　　　　　　353
第 17 章 LR 解析　　　　　　　 358
17.1 上下文无关文法转换为
NPDA　　　　　　　　 359
17.2 项和闭包　　　　　　　　364
17.3 DFA 建模 LR 解析栈　　　 368
17.4 LR(1) 分析表　　　　　 381
17.4.1 LR(1) 的解析动作　　　 381
17.4.2 LR(1) 分析表算法　　　 381
17.5 LR(1) 解析算法　　　　　 388
17.6 带有 λ-产生式的 LR(1)
解析　　　　　　　　 394
17.7 LR(1) 解析冲突　　　　　 404
附录 A 有穷状态转换器　　　　　　410
附录 B 实用工具 JFLAP　　　　　 425
练习题选解　　　　　　　　　　 426
参考文献　　　　　　　　　　 478