第1章 基础知识1
1.1 集合,关系和函数1
1.2 证明方法4
1.3 图6
1.4 语言:基本概念7
问题与解答10
习题12
第2章 文法14
2.1 文法的定义和分类15
2.2 二义性24
2.3 CFG的化简28
2.4 范式31
问题和解答36
习题39
第3章 有限状态自动机44
3.1 确定有限状态自动机(DFSA)45
3.2 不确定有限状态自动机(NFSA)47
3.3 正则表达式51
问题与解答56
习题61
第4章 有限自动机:特征、性质和可判定性65
4.1 有限自动机和正则文法65
4.2 正则集的泵浦引理66
4.3 封闭性68
4.4 可判定性定理70
问题和解答71
习题71
第5章 带输出的有限状态自动机及其最小化73
5.1 Myhill鄄Nerode定理73
5.2 带输出的有限自动机77
问题与解答79
习题81
第6章 有限自动机的变形83
6.1 双向有限自动机83
6.2 多头有限状态自动机88
6.3 概率有限自动机89
6.4 加权有限自动机和数字图像92
问题与解答105
习题108
第7章 下推自动机110
7.1 下推自动机110
7.2 空栈接受和终态接受的等价113
7.3 CFG和PDA的等价114
问题与解答121
习题124
第8章 上下文无关文法性质与分析126
8.1 CFL的泵引理126
8.2 CFL的封闭性127
8.3 CFL的判定性质130
8.4 CFL的子群132
8.5 帕里克映射与帕里克定理134
8.6 自嵌入性138
8.7 同态下的特性139
问题与解答141
习题144
第9章 图灵机147
9.1 作为接受器的图灵机148
9.2 作为计算设备的图灵机157
9.3 图灵机的构造技术164
问题与解答168
习题172
第10章 图灵机的变形175
10.1 通用版本175
10.2 受限图灵机179
10.3 作为枚举器的图灵机181
10.4 图灵机和0型语言的等价182
10.5 线性有界自动机183
10.6 歌德尔编号184
问题与解答185
习题187
第11章 通用图灵机及可判定性189
11.1 图灵机的编码和枚举189
11.2 递归和递归可枚举集189
11.3 通用图灵机192
11.4 问题,实例和语言195
11.5 莱斯定理195
11.6 规约问题以证明不可判定性197
11.7 波斯特对应问题198
11.8 可计算函数204
问题与解答208
习题209
第12章 时间与空间复杂度211
12.1 RAM模型211
12.2 图灵机的时间与带复杂度214
问题与解答228
习题232
第13章 最近的趋势及应用233
13.1 正则重写233
13.2 马库斯上下文文法241
13.3 林登麦伊尔系统248
13.4 文法系统及分布式自动机256
第14章 一些新的计算模型273
14.1 DNA计算273
14.2 膜计算282
单项选择题(I)296
答案303
单项选择题(II)304
答案311
参考文献312
· · · · · · (收起)