计算理论导引 （第2版）

1 (p1): 第0章 绪论
1 (p1-1): 0.1 自动机、可计算性与复杂性
1 (p1-1-1): 0.1.1 计算复杂性理论
2 (p1-1-2): 0.1.2 可计算性理论
2 (p1-1-3): 0.1.3 自动机理论
2 (p1-2): 0.2 数学概念和术语
2 (p1-2-1): 0.2.1 集合
3 (p1-2-2): 0.2.2 序列和多元组
4 (p1-2-3): 0.2.3 函数和关系
6 (p1-2-4): 0.2.4 图
7 (p1-2-5): 0.2.5 字符串和语言
8 (p1-2-6): 0.2.6 布尔逻辑
9 (p1-2-7): 0.2.7 数学名词汇总
10 (p1-3): 0.3 定义、定理和证明
12 (p1-4): 0.4 证明的类型
12 (p1-4-1): 0.4.1 构造性证明
13 (p1-4-2): 0.4.2 反证法
13 (p1-4-3): 0.4.3 归纳法
15 (p1-5): 练习
16 (p1-6): 问题
17 (p1-7): 习题选解
19 (p2): 第一部分 自动机与语言
19 (p2-1): 第1章 正则语言
19 (p2-1-1): 1.1 有穷自动机
21 (p2-1-1-1): 1.1.1 有穷自动机的形式化定义
22 (p2-1-1-2): 1.1.2 有穷自动机举例
24 (p2-1-1-3): 1.1.3 计算的形式化定义
24 (p2-1-1-4): 1.1.4 设计有穷自动机
26 (p2-1-1-5): 1.1.5 正则运算
28 (p2-1-2): 1.2 非确定性
31 (p2-1-2-1): 1.2.1 非确定型有穷自动机的形式化定义
32 (p2-1-2-2): 1.2.2 NFA与DFA的等价性
35 (p2-1-2-3): 1.2.3 在正则运算下的封闭性
37 (p2-1-3): 1.3 正则表达式
38 (p2-1-3-1): 1.3.1 正则表达式的形式化定义
39 (p2-1-3-2): 1.3.2 与有穷自动机的等价性
46 (p2-1-4): 1.4 非正则语言
50 (p2-1-5): 练习
54 (p2-1-6): 问题
58 (p2-1-7): 习题选解
63 (p2-2): 第2章 上下文无关文法
63 (p2-2-1): 2.1 上下文无关文法概述
64 (p2-2-1-1): 2.1.1 上下文无关文法的形式化定义
65 (p2-2-1-2): 2.1.2 上下文无关文法举例
65 (p2-2-1-3): 2.1.3 设计上下文无关文法
66 (p2-2-1-4): 2.1.4 歧义性
67 (p2-2-1-5): 2.1.5 乔姆斯基范式
69 (p2-2-2): 2.2 下推自动机
70 (p2-2-2-1): 2.2.1 下推自动机的形式化定义
70 (p2-2-2-2): 2.2.2 下推自动机举例
72 (p2-2-2-3): 2.2.3 与上下文无关文法的等价性
76 (p2-2-3): 2.3 非上下文无关语言
79 (p2-2-4): 练习
81 (p2-2-5): 问题
83 (p2-2-6): 习题选解
87 (p3): 第二部分 可计算性理论
87 (p3-1): 第3章 丘奇-图灵论题
87 (p3-1-1): 3.1 图灵机
88 (p3-1-1-1): 3.1.1 图灵机的形式化定义
89 (p3-1-1-2): 3.1.2 图灵机的例子
93 (p3-1-2): 3.2 图灵机的变形
93 (p3-1-2-1): 3.2.1 多带图灵机
94 (p3-1-2-2): 3.2.2 非确定型图灵机
95 (p3-1-2-3): 3.2.3 枚举器
96 (p3-1-2-4): 3.2.4 与其他模型的等价性
97 (p3-1-3): 3.3 算法的定义
97 (p3-1-3-1): 3.3.1 希尔伯特问题
98 (p3-1-3-2): 3.3.2 描述图灵机的术语
100 (p3-1-4): 练习
101 (p3-1-5): 问题
102 (p3-1-6): 习题选解
104 (p3-2): 第4章 可判定性
104 (p3-2-1): 4.1 可判定语言
104 (p3-2-1-1): 4.1.1 与正则语言相关的可判定性问题
106 (p3-2-1-2): 4.1.2 与上下文无关语言相关的可判定性问题
108 (p3-2-2): 4.2 停机问题
109 (p3-2-2-1): 4.2.1 对角化方法
111 (p3-2-2-2): 4.2.2 停机问题是不可判定的
113 (p3-2-2-3): 4.2.3 一个图灵不可识别语言
114 (p3-2-3):…