译者序 1
第一章 语言及其表示法 1
1.1 字母表和语言 1
1.2 过程和算法 2
原序 3
1.3 语言的表示 6
习题 8
第二章 文法 10
2.1 启示 10
2.2 文法的形式概念 12
2.3 文法的类型 16
2.4 空句子 19
2.5 前后文有关文法的递归性 22
2.6 前后文无关文法的派生树 24
习题 32
本章参考文献 33
第三章 有穷自动机和正规文法 34
3.1 有穷自动机 34
3.2 等价关系和有穷自动机 36
3.3 不确定的有穷自动机 39
3.4 有穷自动机和3型语言 44
3.5 3型语言的性质 47
3.6 关于有穷自动机的可解问题 53
3.7 双向有穷自动机 55
习题 60
本章参考文献 61
第四章 前后文无关文法 62
4.1 前后文无关文法的简化 62
4.2 Chomsky范式 68
4.3 Greibach范式 71
4.4 有穷性的可解性和“uvwxy定理” 76
4.5 自嵌套特性 82
4.6 前后文无关文法中的б规则 83
4.7 前后文无关语言和文法的特殊类型 85
习题 87
本章参考文献 89
第五章 下推自动机 91
5.1 非形式的描述 91
5.2 定义 93
5.3 不确定的下推自动机和前后文无关语言 99
习题 105
本章参考文献 106
6.2 定义和记号 107
第六章 图灵机 107
6.1 引言 107
6.3 图灵机的构造技术 111
6.4 图灵机作为过程 121
6.5 图灵机的修改 123
6.6 等价于基本模型的受限图灵机 131
习题 134
本章参考文献 135
第七章 图灵机：停机问题 0型语言 136
7.1 非形式的讨论 136
7.2 通用图灵机 136
7.3 停机问题的不可解性 142
7.4 递归集类 144
7.5 图灵机和0型文法 145
习题 149
本章参考文献 150
第八章 线性界限自动机与前后文有关语言 151
8.1 引言 151
8.2 线性界限自动机与前后文有关语言的关系 152
8.3 前后文有关语言是递归集的子类 154
习题 155
本章参考文献 156
第九章 对语言的运算 157
9.1 引言 157
9.2 对基本运算的封闭性 157
9.3 对映射的封闭性 162
习题 174
本章参考文献 175
10.2 定义 177
10.1 引言 177
第十章 时间界限和带界限的图灵机 177
10.3 “加速”定理和“缩带”定理 179
10.4 单带图灵机和交叉序列 187
10.5 带复杂度的下界 192
10.6 带谱系和时间谱系 196
习题 202
本章参考文献 203
第十一章 识别前后文无关语言时的时空界限 204
11.1 引言 204
11.2 识别前后文无关语言时的时间要求 204
11.3 识别前后文无关语言时的空间要求 210
习题 215
本章参考文献 216
12.1 引言 217
第十二章 确定的下推自动机 217
12.2 确定的语言的补集 218
12.3 确定的语言的性质 224
12.4 不确定的前后文无关语言 235
12.5 LR(k)文法 236
习题 245
本章参考文献 246
第十三章 堆栈自动机 247
13.1 定义 247
13.2 堆栈自动机的受限型 251
13.3 双向堆栈自动机的力量 252
13.4 单向堆栈自动机的力量 263
13.5 堆栈自动机的递归性 271
13.6 封闭性 272
本章参考文献 274
习题 274
第十四章 可判定性 275
14.1 可解的和不可解的问题 275
14.2 Post的对应问题 276
14.3 有关前后文有关语言的一个问题 285
14.4 前后文无关语言的不可解的问题 286
14.5 前后文无关语言的歧义性 289
14.6 有关确定的前后文无关语言的不可解的问题 300
14.7 对正规文法、LR(k)文法、前后文无关文法、前后文有关文法和0型文法的不可解性的总结 301
习题 302
本章参考文献 303
参考文献 304
汉英名词对照 310