形式语言与自动机理论教学参考书(第4版)

“形式语言与自动机理论”是难度较大的课程，虽然其很重要，但因为太难，影响了课程的开设和学生的学习，所以，提供教学参考书很有必要。 本书是第4版，第一版，入选21世纪大学本科计算机专业系列教材，第2、3版先后入选普通高等教育“十一五”国家级规划教材和“十二五”普通高等教育本科国家级规划教材，第2版在2008年还被评为普通高等教育重量精品教材。主要特点有（1） 满足国内外对课程的近期新要求；（2） 适合国情，倡导研究型教学，强化能力培养；（3） 体现学科基本教育原理；（4） 配套建设教学参考书和电子教案；（5） 化解深奥。保持基本内容抽象和形式化特征，设计引导思路的图，通过直观可视化，更清晰地表达思路，并使得内容更易理解。（6） 内容组织合理。不仅考虑知识体系满足本科生和近期研究生教育的基本要求，还考虑有利于反映和传授本学科特有思想方法。删除了一些生僻内容；（7） 习题丰富恰当。每章都附有大量习题。由于国内外的教材比较少，而且内容难度很大，要求习题既不能伤害读者的信心，又能促进读者对课程知识和课程深层内容的理解，并锻炼相关的能力。

本书作为《形式语言与自动机理论（第4版）》（主教材）的配套教学辅导用书，按照主教材的结构编写而成。本书包括有关内容的讲解、学习要点、问题分析、求解思路和方法、注意事项。考虑到该课程习题求解具有相当的难度，以及给出全部习题解答又不利于学生学习，本书只给出了典型习题的解析。为了引导读者及时总结学习内容，按照小节给出知识点和主要内容解读，为读者学习和掌握主教材中的知识点和问题求解方法，体会问题求解的核心思想提供帮助，对教师和学生来说，阅读这些内容都是很有意义的。

第1章绪论1
1.1集合的基础知识2
1.1.1集合及其表示2
1.1.2集合之间的关系3
1.1.3集合的运算4
1.2关系5
1.2.1二元关系5
1.2.2递归定义与归纳证明6
1.2.3关系的闭包6
1.3图7
1.3.1无向图7
1.3.2有向图8
1.3.3树8
1.4语言9
1.4.1什么是语言9
1.4.2形式语言与自动机理论的产生与作用10
1.4.3基本概念11
1.5小结14
1.6典型习题解析14
第2章文法20
2.1启示21
2.2形式定义22
2.3文法的构造26
2.4文法的乔姆斯基体系29
2.5空语句32
2.6小结33
2.7典型习题解析33
第3章有穷状态自动机45
3.1语言的识别46
3.2有穷状态自动机46
3.3不确定的有穷状态自动机51
3.3.1作为对DFA的修改51
3.3.2NFA的形式定义51
3.3.3NFA与DFA等价52
3.4带空移动的有穷状态自动机55
3.5FA是正则语言的识别器57
3.5.1FA与右线性文法57
3.5.2FA与左线性文法58
3.6FA的一些变形60
3.6.1双向有穷状态自动机60
3.6.2带输出的FA61
3.7小结62
3.8典型习题解析63
第4章正则表达式70
4.1启示70
4.2正则表达式的形式定义71
4.3正则表达式与FA等价73
4.3.1正则表达式到FA的等价变换73
4.3.2正则语言可以用正则表达式表示75
4.4正则语言等价模型的总结77
4.5小结78
4.6典型习题解析79
第5章正则语言的性质83
5.1正则语言的泵引理84
5.2正则语言的封闭性85
5.3Myhill-Nerode定理与DFA的极小化89
5.3.1Myhill-Nerode 定理89
5.3.2DFA的极小化93
5.4关于正则语言的判定算法95
5.5小结96
5.6典型习题解析96
第6章上下文无关语言103
6.1上下文无关文法104
6.1.1上下文无关文法的派生树104
6.1.2二义性107
6.1.3自顶向下的分析和自底向上的分析109
6.2上下文无关文法的化简110
6.2.1去无用符号110
6.2.2去ε-产生式113
6.2.3去单一产生式116
6.3乔姆斯基范式117
6.4格雷巴赫范式119
6.5自嵌套文法122
6.6小结123
6.7典型习题解析123
第7章下推自动机127
7.1基本定义128
7.2PDA与CFG等价130
7.2.1PDA用空栈接受和用终止状态接受等价130
7.2.2PDA与CFG等价131
7.3小结133
7.4典型习题解析134
第8章上下文无关语言的性质140
8.1上下文无关语言的泵引理141
8.2上下文无关语言的封闭性144
8.3上下文无关语言的判定算法146
8.3.1L空否的判定147
8.3.2L是否有穷的判定147
8.3.3x是否为L的句子的判定148
8.4小结150
8.5典型习题解析150
第9章图灵机152
9.1基本概念153
9.1.1基本图灵机153
9.1.2图灵机作为非负整函数的计算模型157
9.1.3图灵机的构造157
9.2图灵机的变形160
9.2.1双向无穷带图灵机160
9.2.2多带图灵机163
9.2.3不确定的图灵机164
9.2.4多维图灵机165
9.2.5其他图灵机166
9.3通用图灵机168
9.4几个相关的概念170
9.4.1可计算性170
9.4.2P与NP相关问题170
9.5小结171
9.6典型习题解析171
第10章上下文有关语言183
10.1图灵机与短语结构文法的等价性183
10.2线性有界自动机及其与上下文有关文法的等价性186
10.3小结187
10.4典型习题解析187
第11章内容归纳190
11.1文法与语言190
11.2正则语言190
11.3上下文无关语言191
11.4图灵机192
11.5上下文有关语言193
第12章教学设计194
12.1概述194
12.1.1基本描述194
12.1.2教学定位194
12.1.3教学目标195
12.1.4知识点与学时分配196
12.2课堂讲授198
12.2.1重点与难点198
12.2.2讲授中应注意的方法等问题203
12.3作业205
12.3.1指导思想205
12.3.2关于大作业和实验205
12.4课程考试与成绩评定205
12.4.1成绩评定205
12.4.2考题设计207
参考文献209