第1章 预备知识 1
1.1定理及其证明方法 1
演绎法 2
反证法 3
归纳法 5
1.2集合及其基本运算 7
集合基础知识 7
集合的基本运算 8
关系与映射 9
1.3图和树简介 11
图的基本概念 12
图的矩阵表示 13
树的基本知识 15
1.4字母表、字符串和语言 16
习题 18
第2章 文法的一般理论 21
2.1问题的提出 21
2.2形式文法与形式语言 23
2.3文法的乔姆斯基分类 30
习题 40
第3章 有穷自动机 42
3.1非形式化描述 42
3.2有穷自动机的基本定义 44
3.3非确定的有穷自动机 48
3.4具有ε转移的有穷自动机 52
3.5有穷自动机的应用 55
在文本中查找字符串 55
用于文本搜索的非确定的有穷自动机 55
识别关键字集合的DFA 56
3.6具有输出的有穷自动机 58
习题 60
第4章 正则表达式 63
4.1正则表达式的定义 63
4.2正则表达式和有穷自动机的关系 65
4.3正则表达式的等价变换 70
交换律与结合律 70
单位元与零元 71
分配律 71
与“＊”构造有关的定律 72
发现正则表达式定律的一般方法 73
4.4正则表达式的应用 75
UNIX中的正则表达式 75
词法分析 76
查找文本中的模式 77
习题 78
第5章 正则语言的性质 80
5.1正则文法和有穷自动机的关系 80
5.2正则语言的泵引理 82
5.3正则语言的封闭性 85
5.4正则语言的判定算法 89
5.5有穷自动机的最小化 91
习题 99
第6章 上下文无关文法 101
6.1上下文无关文法的语法分析 101
6.2上下文无关文法的化简 107
6.3上下文无关文法的范式 111
6.4上下文无关文法的应用 115
用上下文无关文法描述语言 115
语法分析器生成工具YACC 116
标记语言 117
XML和文档类型定义 118
习题 121
第7章 下推自动机 124
7.1下推自动机的定义 124
7.2下推自动机接受的语言 125
7.3下推自动机和上下文无关文法的关系 130
7.4确定的下推自动机 134
习题 135
第8章 上下文无关语言的性质 136
8.1上下文无关语言的泵引理 136
8.2上下文无关语言的封闭性 141
8.3上下文无关语言的判定算法 142
习题 146
第9章 图灵机导引 148
9.1图灵机的基本模型 148
9.2图灵机的程序设计技术 154
在状态中存储符号 154
多道技术 155
子程序技术 159
9.3图灵机的变形 161
双向无限带 161
多带 162
非确定的图灵机 165
双栈机 166
作为枚举器的图灵机 167
9.4图灵机与计算机 169
用计算机模拟图灵机 169
用图灵机模拟计算机 170
比较计算机与图灵机的运行时间 172
9.5图灵机与0型文法的关系 173
习题 176
第10章 不可判定性 178
10.1递归集和递归可枚举集的性质 178
10.2通用图灵机和第一个不可判定问题 180
10.3归约方法和莱斯定理 183
10.4关于上下文无关语言的不可判定问题 188
10.5波斯特对应问题的不可判定性及其应用 191
习题 197
第11章 线性有界自动机和上下文有关文法 199
11.1线性有界自动机 199
11.2线性有界自动机和上下文有关文法的关系 201
11.3上下文有关语言的性质及其与递归集的关系 202
11.4各语言类之间的关系 204
习题 205
第12章 确定的上下文无关语言和LR（k）文法 206
12.1确定的下推自动机的标准形式 206
12.2确定的上下文无关语言的性质 207
12.3 LR（0）文法 212
12.4 LR（0）文法与DPDA的关系 216
12.5 LR（k）文法 221
习题 226
参考文献 228