第1章绪论1
1.1集合的基础知识2
1.1.1集合及其表示2
1.1.2集合之间的关系3
1.1.3集合的运算4
1.2关系6
1.2.1二元关系6
1.2.2递归定义与归纳证明7
1.2.3关系的闭包7
1.3图8
1.3.1无向图8
1.3.2有向图9
1.3.3树10
1.4语言11
1.4.1什么是语言11
1.4.2形式语言与自动机理论的产生与作用12
1.4.3基本概念14
1.5小结17
1.6典型习题解析17
第2章文法24
2.1启示25
2.2形式定义27
2.3文法的构造31
2.4文法的乔姆斯基体系35
2.5空语句39
2.6小结40
2.7典型习题解析41
第3章有穷状态自动机54
3.1语言的识别55
3.2有穷状态自动机55
3.3不确定的有穷状态自动机61
3.3.1作为对DFA的修改61
3.3.2NFA的形式定义61
3.3.3NFA与DFA等价63
3.4带空移动的有穷状态自动机66
3.5FA是正则语言的识别器68
3.5.1FA与右线性文法68
3.5.2FA与左线性文法70
3.6FA的一些变形72
3.6.1双向有穷状态自动机72
3.6.2带输出的FA73
3.7小结75
3.8典型习题解析76
第4章正则表达式84
4.1启示85
4.2正则表达式的形式定义85
4.3正则表达式与FA等价87
4.3.1正则表达式到FA的等价变换87
4.3.2正则语言可以用正则表达式表示90
4.4正则语言等价模型的总结92
4.5小结94
4.6典型习题解析95
第5章正则语言的性质99
5.1正则语言的泵引理100
5.2正则语言的封闭性101
5.3Myhill\|Nerode定理与DFA的极小化106
5.3.1Myhill\|Nerode定理106
5.3.2DFA的极小化111
5.4关于正则语言的判定算法113
5.5小结114
5.6典型习题解析115
第6章上下文无关语言123
6.1上下文无关文法124
6.1.1上下文无关文法的派生树125
6.1.2二义性128
6.1.3自顶向下的分析和自底向上的分析131
6.2上下文无关文法的化简131
6.2.1去无用符号132
6.2.2去ε\|产生式136
6.2.3去单一产生式139
6.3乔姆斯基范式140
6.4格雷巴赫范式142
6.5自嵌套文法146
6.6小结147
6.7典型习题解析148
第7章下推自动机152
7.1基本定义153
7.2PDA与CFG等价155
7.2.1PDA用空栈接受和用终止状态接受等价155
7.2.2PDA与CFG等价157
7.3小结159
7.4典型习题解析160
第8章上下文无关语言的性质167
8.1上下文无关语言的泵引理168
8.2上下文无关语言的封闭性171
8.3上下文无关语言的判定算法175
8.3.1L空否的判定175
8.3.2L是否有穷的判定176
8.3.3x是否为L的句子的判定177
8.4小结179
8.5典型习题解析179
第9章图灵机182
9.1基本概念183
9.1.1基本图灵机184
9.1.2图灵机作为非负整函数的计算模型188
9.1.3图灵机的构造189
9.2图灵机的变形192
9.2.1双向无穷带图灵机193
9.2.2多带图灵机196
9.2.3不确定的图灵机198
9.2.4多维图灵机199
9.2.5其他图灵机200
9.3通用图灵机203
9.4几个相关的概念204
9.4.1可计算性204
9.4.2P与NP相关问题205
9.5小结206
9.6典型习题解析206
第10章上下文有关语言220
10.1图灵机与短语结构文法的等价性220
10.2线性有界自动机及其与上下文有关文法的等价性223
10.3小结225
10.4典型习题解析225
第11章内容归纳229
11.1文法与语言229
11.2正则语言229
11.3上下文无关语言230
11.4图灵机231
11.5上下文有关语言232
第12章教学设计233
12.1概述233
12.2课程内容体系234
12.2.1课程的基本描述234
12.2.2教学定位235
12.2.3知识点与学时分配236
12.3讲授提示238
12.3.1重点与难点238
12.3.2讲授中应注意的方法等问题242
12.4习题与实验243
12.4.1指导思想243
12.4.2关于大作业和实验243
12.5考试与成绩记载244
12.5.1成绩评定244
12.5.2考题设计244
参考文献246
