形式语言与自动机理论教学参考书

内容概要

北京工业大学教授，1978年3月至1984年7月在哈尔滨工业大学计算机学科学习，先后到美国、加拿大进修，1984年、1985年先后在哈尔滨工业大学和北京工业大学主讲编译原理、形式语言与自动机理论等课程。从事网络计算、操作系统、人工神经网络和计算机科学与技术学科的教育教学等研究，发表了大量研究论文，参加起草计算机科学与技术专业规范、认证文件、计算机技术工程领域硕士研究生培养基本要求等。    北京市教学名师，国家精品课程和北京市精品课程“编译原理”负责人，主编的《形式语言与自动机理论(第2版)》为国家2008年度普通高等教育精品教材，国家优秀教学团队负责人。获国家教学成果二等奖2项，北京市教学成果一等奖3项，二等奖1项，另有多项省部级教学、科研成果一、二、三等奖。曾获中国高校优秀青年学者、宝钢优秀教师、航天部优秀青年教师等荣誉称号。    主要学术兼职有全国工程教育专业认证专家委员会计算机类专业认证试点工作组成员、教育部高校计算机专业教学指导分委员会秘书长、中国计算机学会教育专委主任兼本科组组长、中国计算机学会教育工委副主任、全国高校计算机教育研究会副理事长。

书籍目录

第1章 绪论 11.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.2 NFA的形式定义51  3.3.3 NFA与DFA等价52 3.4 带空移动的有穷状态自动机55 3.5 FA是正则语言的识别器57  3.5.1 FA与右线性文法57  3.5.2 FA与左线性文法58 3.6 FA的一些变形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.3 MyhillNerode定理与DFA的极小化89  5.3.1 MyhillNerode定理89  5.3.2 DFA的极小化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.2 PDA与CFG等价130  7.2.1 PDA用空栈接受和用终止状态接受等价130  7.2.2 PDA与CFG等价131 7.3 小结133 7.4 典型习题解析134第8章 上下文无关语言的性质140 8.1 上下文无关语言的泵引理141 8.2 上下文无关语言的封闭性144 8.3 上下文无关语言的判定算法146  8.3.1 L空否的判定147  8.3.2 L是否有穷的判定147  8.3.3 x是否为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.2 P与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第12章 教学设计194 12.1 概述194 12.2 课程内容体系195  12.2.1 课程的基本描述195  12.2.2 教学定位195  12.2.3 知识点与学时分配196 12.3 讲授提示198  12.3.1 重点与难点198  12.3.2 讲授中应注意的方法等问题201 12.4 习题与实验202  12.4.1 指导思想202  12.4.2 关于大作业和实验202  2.5 考试与成绩记载202  12.5.1 成绩评定202  12.5.2 考题设计203参考文献204

编辑推荐

蒋宗礼编著的《形式语言与自动机理论教学参考书(第3版）》共分12章。为了便于阅读，从第1章到第10章完全与原书结构相对应。第1章回顾在离散数学中学过的本书将要用到的一些基础知识，为后续的章节做好准备。由于主要是为了复习，所以这里给出的是知识点和应该注意的事项。除最后一节的“形式语言及其相关的基本概念”为新内容外，其他内容都可以由学生自学。第2章到第8章是教学的重点内容，主要讨论正则语言和上下文无关语言的文法、自动机描述及其性质。第9章对计算进行介绍，包括一般计算模型图灵机的概念、构造方法、修改，与计算相关的不可判定性、P\|NP等问题。第10章介绍上下文有关语言。在这些章节中，以知识点、主要内容解读、典型习题解析的形式，对讨论的内容进行归纳和解析。第11章对本书的内容按类进行全面总结。在第12章中安排了教学设计，从总体上讨论本课程的讲授等问题。

作者简介

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



《形式语言与自动机理论教学参考书(第3版）》由蒋宗礼编著。

---

 形式语言与自动机理论教学参考书下载

---