目录 1
第1章 预备知识 1
1.1 集合及其运算 1
1.2 证明和证明方法 7
1.3 字母表、字符串和语言 12
习题 14
第2章 文法理论 17
2.1 问题的提出 17
2.2 文法的形式定义及分类 20
2.3 文法的几个有关概念 29
习题 42
第3章 有穷自动机和正规表达式 45
3.1 有穷自动机的背景和基本定义 45
3.2 非确定的有穷自动机 50
3.3 具有ε动作的有穷自动机 56
3.4 正规表达式和正规集 61
3.5 具有输出的有穷自动机 71
习题 75
第4章 正规文法与正规集的性质 79
4.1 正规文法与有穷自动机的关系 79
4.2 正规集的缩胀定理 82
4.3 正规集的封闭性质与判定算法 87
4.4 有穷自动机的极小化 92
习题 106
第5章 上下文无关文法与下推自动机 109
5.1 上下文无关文法的化简 109
5.2 上下文无关文法的范式 116
5.3 下推自动机 122
5.4 下推自动机与上下文无关文法的关系 129
习题 134
6.1 上下文无关语言的缩胀定理 136
第6章 上下文无关语言的性质 136
6.2 上下文无关语言的封闭性质 145
6.3 上下文无关语言的判定算法 148
习题 154
第7章 图灵机 156
7.1 图灵机的基本模型 156
7.2 图灵机的构造技术 164
7.3 图灵机的变型 174
7.4 图灵机与0型文法的关系 185
习题 189
第8章 不可判定性 191
8.1 递归集和递归可枚举集的性质 192
8.2 通用图灵机和两个不可判定问题 195
8.3 归约方法和Rice定理 200
8.4 关于CFL的不可判定问题 207
8.5 Post对应问题的不可判定性及其应用 213
习题 220
第9章 线性有界自动机和上下文有关语言 223
9.1 线性有界自动机 223
9.2 线性有界自动机和上下文有关文法的关系 225
9.3 上下文有关语言的性质及其与递归集的关系 228
9.4 语言类之间的关系 231
习题 233
第10章 确定的下推自动机与LR(k)文法 234
10.1 确定的下推自动机及其标准形式 234
10.2 确定的上下文无关语言的性质 237
10.3 LR(O)文法 245
10.4 LR(O)文法与DPDA的关系 252
10.5 LR(k)文法 261
习题 271
参考文献 273