包邮形式语言与自动机理论(第4版)

目录CONTENTS 第1章绪论1 1.1集合的基础知识2 1.1.1集合及其表示2 1.1.2集合之间的关系4 1.1.3集合的运算5 1.2关系10 1.2.1二元关系10 1.2.2等价关系与等价类11 1.2.3关系的合成12 1.2.4递归定义与归纳证明13 1.2.5关系的闭包15 1.3图16 1.3.1无向图16 1.3.2有向图17 1.3.3树19 1.4语言20 1.4.1什么是语言20 1.4.2形式语言与自动机理论的产生与作用21 1.4.3基本概念23 1.5小结29 习题29 第2章文法36 2.1启示37 2.2形式定义39 2.3文法的构造47 2.4文法的乔姆斯基体系55 2.5空语句65 2.6小结67 习题68 第3章有穷状态自动机71 3.1语言的识别71 3.2有穷状态自动机73 3.3不确定的有穷状态自动机84 3.3.1作为对DFA的修改84 3.3.2NFA的形式定义86 3.3.3NFA与DFA等价92 3.4带空移动的有穷状态自动机96 3.5FA是正则语言的识别器100 3.5.1FA与右线性文法100 3.5.2FA与左线性文法104 3.6FA的一些变形105 3.6.1双向有穷状态自动机105 3.6.2带输出的FA107 3.7小结108 习题108 第4章正则表达式114 4.1启示114 4.2正则表达式的形式定义115 4.3正则表达式与FA等价117 4.3.1正则表达式到FA的等价变换117 4.3.2正则语言可以用正则表达式表示125 4.4正则语言等价模型的总结130 4.5小结131 习题132第5章正则语言的性质134 5.1正则语言的泵引理134 5.2正则语言的封闭性139 5.3MyhillNerode定理与DFA的极小化145 5.3.1MyhillNerode定理146 5.3.2DFA的极小化154 5.4关于正则语言的判定算法161 5.5小结163 习题163 第6章上下文无关语言166 6.1上下文无关文法166 6.1.1上下文无关文法的派生树167 6.1.2二义性172 6.1.3自顶向下的分析和自底向上的分析175 6.2上下文无关文法的化简177 6.2.1去无用符号178 6.2.2去ε产生式181 6.2.3去单一产生式组184 6.3乔姆斯基范式187 6.4格雷巴赫范式190 6.5自嵌套文法195 6.6小结196 习题196 第7章下推自动机200 7.1基本定义200 7.2PDA与CFG等价206 7.2.1PDA用空栈接受和用终止状态接受等价206 7.2.2PDA与CFG等价209 7.3小结218 习题219 第8章上下文无关语言的性质221 8.1上下文无关语言的泵引理221 8.2上下文无关语言的封闭性227 8.3上下文无关语言的判定算法232 8.3.1L空否的判定232 8.3.2L是否有穷的判定233 8.3.3x是否为L的句子的判定234 8.4小结236 习题236 第9章图灵机238 9.1基本概念239 9.1.1基本图灵机239 9.1.2图灵机作为非负整函数的计算模型246 9.1.3图灵机的构造248 9.2图灵机的变形255 9.2.1双向无穷带图灵机255 9.2.2多带图灵机258 9.2.3不确定的图灵机260 9.2.4多维图灵机261 9.2.5其他图灵机263 9.3通用图灵机265 9.4几个相关的概念267 9.4.1可计算性267 9.4.2P与NP相关问题267 9.5小结268 习题268 第10章上下文有关语言272 10.1图灵机与短语结构文法的等价性272 10.2线性有界自动机及其与上下文有关文法的等价性275 10.3小结276 习题277 附录A教学设计278 A.1课程概述278 A.1.1基本描述278 A.1.2教学定位278 A.1.3教学目标279 A.1.4知识点与学时分配280 A.2课堂讲授282 A.2.1重点与难点282 A.2.2讲授中应注意的方法等问题287 A.3作业289 A.3.1指导思想289 A.3.2关于大作业和实验289 A.4课程考试与成绩评定289 A.4.1成绩评定289 A.4.2考题设计291 附录B缩写符号293 词汇索引295 参考文献302