目录 1
第一章 有限自动机的逻辑网络实现 1
1.1有限自动机的定义 1
1.2逻辑网络的定义 5
1.3有限自动机与合式网络的等价性 13
习题 19
第二章 状态化简 26
2.1有限自动机的极小化 26
22状态等价类的求法 32
2.3偏有限自动机的极小化 36
习题 46
第三章 正规集 55
3.1有限识别器和迁移图的等价性 55
3.2基本定理 64
3.3正规集的封闭性质 70
习题 73
第四章 线性有限自动机 80
4.1初等性质 80
4.2状态化简和标准化 87
4.3z变换 101
习题 111
第五章 自治有限自动机 116
5.1一般情形 116
5.2线性情形 119
习题 128
第六章 状态识别试验 132
6.1初态试验序列 132
6.2末态试验序列 138
6.3同步序列 141
习题 144
第七章 存贮性 147
7.1输入输出存贮 147
7.2输入存贮 153
习题 158
第八章 可逆性 162
8.1有限延迟性和逆的存在性 162
8.2误差传播与前馈可逆 172
习题 179
第九章 通用自动机 184
9.1自动机的定义 184
9.2归约 190
9.3定长字变换 205
9.4两种通用自动机 210
习题 221
第十章 图灵机 224
10.1图灵机的定义 224
10.2图灵机与自动机的等价性 231
习题 241
11.1递归函数的可计算性 247
第十一章 递归函数 247
11.2可计算函数的递归性 259
11.3自然数上递归函数 272
11.4半可计算谓词与自动机可识别集 279
习题 283
第十二章 不可判定问题 288
12.1停机问题 288
12.2波斯特对应问题 290
习题 293
第十三章 时空限制下的计算 295
13.1阿克曼函数时间界限下的计算 295
13.2阿克曼函数空间界限下的计算 309
13.3复杂性类之间的关系、Pr和Pr（θ）的分层 313
习题 323
常用符号和术语 325
参考文献 331