第1章 数学基础 1
1.1 引言 1
1.2 集合 1
1.3 关系与图 3
1.4 函数与计数 7
1.5 证明技巧 14
1.6 本章总结与习题 22
本章习题 22
第2章 正则语言 26
2.1 引言 26
2.2 语言基础 26
本节习题 29
2.3 正则表达式 31
本节习题 32
2.4 正则语法 34
本节习题 37
2.5 确定性有限自动机（DFA） 38
本节习题 46
2.6 非确定性有限自动机（NFA） 47
本节习题 52
2.7 本章总结与附加思考题 54
附加思考题 54
第3章 等价 58
3.1 引言 58
3.2 NFA到DFA 58
本节习题 63
3.3 有限自动机与正则语法 64
本节习题 65
3.4 正则表达式到NFA 66
本节习题 68
3.5 NFA到正则表达式 69
本节习题 73
3.6 本章总结与附加思考题 75
附加思考题 76
第4章 正则语言的结构 78
4.1 引言 78
4.2 闭包性质 78
本节习题 81
4.3 非正则语言 82
本节习题 86
4.4 米歇尔-尼罗德定理 88
本节习题 92
4.5 状态最小化 92
本节习题 98
4.6 本章总结与附加思考题 99
附加思考题 100
第5章 上下文无关语言 105
5.1 引言 105
5.2 上下文无关语法 105
本节习题 108
5.3 分析树 110
本节习题 114
5.4 歧义 114
本节习题 117
5.5 消除／删除不良生成式 118
本节习题 121
5.6 范式 122
本节习题 128
5.7 本章总结与附加思考题 129
附加思考题 129
第6章 上下文无关语言的结构 132
6.1 引言 132
6.2 叠加自动机 132
本节习题 138
6.3 上下文无关语法与叠加自动机 140
本节习题 144
6.4 泵作用引理 145
本节习题 150
6.5 上下文无关语言的闭包性质 151
本节习题 153
6.6 确定型叠加自动机 154
本节习题 158
6.7 本章总结与附加思考题 159
附加思考题 159
第7章 可计算枚举语言 167
7.1 引言 167
7.2 非限制性语法 167
本节习题 169
7.3 图灵机 170
本节习题 174
7.4 接受与拒绝 174
本节习题 179
7.5 使用旧自动机 180
本节习题 187
7.6 多带图灵机 188
本节习题 191
7.7 非确定性图灵机和语法 192
本节习题 197
7.8 本章总结与附加思考题 198
附加思考题 198
第8章 非可计算枚举语言 201
8.1 引言 201
8.2 作为计算器的图灵机 201
本节习题 204
8.3 作为语言判定的图灵机 205
本节习题 209
8.4 存在多少图灵机 210
本节习题 213
8.5 接受问题 213
本节习题 217
8.6 乔姆斯基层次结构 217
本节习题 219
8.7 总结和附加问题 222
本节习题 222
第9章 算法可解性 229
9.1 引言 229
9.2 问题归约 230
本节习题 232
9.3 赖斯定理 234
本节习题 236
9.4 关于有限自动机 238
本节习题 239
9.5 关于叠加自动机 240
本节习题 244
9.6 关于波斯特对应问题 245
本节习题 249
9.7 关于逻辑理论 250
本节习题 255
9.8 其他有趣的问题 255
本节习题 257
9.9 总结和附加问题 258
本节习题 259
第10章 计算复杂性 267
10.1 引言 267
10.2 函数增长率 268
本节习题 271
10.3 复杂性类别 272
本节习题 275
10.4 空间复杂性 276
本节习题 278
10.5 时间复杂性 279
本节习题 283
10.6 NP类 284
本节习题 286
10.7 NP完整性 287
本节习题 291
10.8 某些NP完整问题 291
本节习题 298
10.9 解决NP完整问题 300
本节习题 303
10.10 本章总结与附加思考题 303
附加思考题 304
部分习题答案与提示 313
参考文献 334