第1章 计算理论基础 1
1.1 集合的基本概念 1
1.1.1 集合的定义 1
1.1.2 集合的表示 1
1.1.3 集合间的关系 1
1.1.4 集合的运算 2
1.2 关系 3
1.2.1 二元关系 3
1.2.2 二元关系的性质 3
1.2.3 等价关系 3
1.2.4 递归定义与归纳证明 4
1.3 图与树 6
1.3.1 无向图 7
1.3.2 有向图 7
1.3.3 树 8
1.3.4 二叉树 8
1.4 三个重要概念 9
习题 10
第2章 文法与语言 13
2.1 启示 13
2.2 文法的形式定义 14
2.3 文法的构造 15
2.4 文法的Chomsky体系 16
习题 18
第3章 上下文无关文法及其语言 20
3.1 上下文无关文法 20
3.1.1 派生与派生树 20
3.1.2 文法的二义性 23
3.2 文法和语言的讨论 24
3.3 句法分析 27
3.3.1 最左派生和不确定性 27
3.3.2 文法图 28
3.3.3 广度优先自顶向下句法分析 29
3.3.4 深度优先自顶向下分析 30
3.3.5 自底向上分析 32
3.4 上下文无关文法的化简 38
3.4.1 无用符号 38
3.4.2 消除ε产生式 38
3.4.3 消除单一产生式 39
3.4.4 消除左递归 40
3.5 Chomsky范式 44
3.6 Greibach范式 46
习题 48
第4章 有穷状态自动机 54
4.1 语言的识别 54
4.2 有穷状态自动机的形式定义 55
4.3 确定的有穷自动机 55
4.4 状态转换图 57
4.5 不确定的有穷自动机 58
4.6 NFA与DFA的等价 60
4.7 带空转移的NFA 63
4.8 ε-NFA的确定化 65
4.9 DFA最小化 66
习题 70
第5章 正则语言和正则文法 73
5.1 正则表达式 73
5.1.1 正则表达式的定义 73
5.1.2 正则语言 73
5.2 有穷自动机和正则语言 74
5.2.1 正则表达式到有穷自动机 74
5.2.2 有穷自动机到正则表达式 76
5.3 正则文法和有穷自动机 78
5.3.1 正则文法 78
5.3.2 正则文法与NFA 81
习题 85
第6章 正则语言的性质 87
6.1 正则语言的封闭性 87
6.1.1 简单运算的封闭性 87
6.1.2 其他运算的封闭性 88
6.2 非正则语言的识别 91
6.2.1 鸽巢原理 92
6.2.2 泵引理 92
6.3 Myhill Nerode定理 94
6.4 正则语言的判定算法 99
习题 100
第7章 下推自动机与上下文无关文法 101
7.1 非确定型下推自动机 101
7.1.1 下推自动机的定义 101
7.1.2 下推自动机接受的语言 102
7.2 下推自动机与上下文无关文法 104
7.2.1 上下文无关语言相应的下推自动机 104
7.2.2 下推自动机与相应的上下文无关文法 106
7.3 确定型下推自动机 109
7.4 双栈自动机 110
习题 111
第8章 上下文无关语言的性质 114
8.1 上下文无关文法的泵引理 114
8.2 上下文无关语言的封闭性 116
8.3 上下文无关语言的可判定性 118
习题 118
第9章 图灵机 120
9.1 标准图灵机 120
9.1.1 图灵机的形式定义 120
9.1.2 图灵机识别器 122
9.1.3 图灵机转换器 124
9.2 完成复杂任务的图灵机 126
习题 128
第10章 图灵机的其他模型 130
10.1 带不动选择图灵机 130
10.2 多道图灵机 131
10.3 单向无穷带图灵机 132
10.4 离线图灵机 133
10.5 多带图灵机 134
10.6 多头图灵机 137
10.7 非确定型图灵机 138
10.8 线性界限自动机 140
习题 141
第11章 其他计算模型 143
11.1 递归函数 143
11.1.1 递归函数 143
11.1.2 递归函数的扩展理解 146
11.2 波斯特系统 148
11.3 重写系统 149
11.3.1 矩阵文法 149
11.3.2 马尔可夫算法 150
习题 151
参考文献 152