形式语言与自动机理论

课程编码：180086081202P3003H 英文名称：Formal Language and Automata Theory. 课时：40 学分：2.00 课程属性：专业课 主讲教师：姚刚

本课程是计算机软件与理论专业的硕士研究生专业普及课。本课程讲授和讨论自动机和形式语言研究领域的主要思想和关键技术。形式语言是研究自然语言和人工语言的数学工具,自动机理论研究抽象计算装置或“机器”。形式语言与自动机理论研究问题的自动化方法是：将问题分为若干基本问题类，给出了各问题类对应的计算模型，通过研究这些模型的性质及其变化方法来对这些问题进行研究。这种“问题-形式化-自动化”的方法和思想是进行计算机问题求解的基本途径，对于计算机科学与技术工作者是非常重要的。另外，形式语言与自动机理论还是研究算法理论的基础。本课程重点讲述具有实用意义的正则语言与有限自动机、上下文无关语言与下推自动机、递归可枚举语言与图灵机，同时还介绍具有理论价值的其他几类语言和自动机，以及计算理论中的不可判定问题和难解问题。通过本课程的学习，希望学生学到计算机科学理论中的一些最基本的方法和思想，掌握形式语言与自动机理论的关键技术，了解自动机和形式语言前沿研究领域，了解自动机和形式语言最新研究成果，培养学生的计算思维能力，为走向深入和广博打下基础。

离散数学

第一章 计算理论导引 姚刚
第1节 数学预备知识和表示 1.2学时
第2节 语言、文法与自动机的基本概念 1.5学时
第3节 课程概览 0.3学时
第二章 有穷接受器与正则语言 姚刚
第1节 有穷接受器的概念 1.5学时
第2节 确定型有穷接受器和非确定型有穷接受器的等价性 1.0学时
第3节 有穷接受器的状态化简 1.0学时
第4节 正则表达式 0.5学时
第5节 正则表达式和正则语言之间的联系 1.0学时
第6节 正则文法 1.0学时
第7节 正则语言的封闭性质 1.8学时
第8节 正则语言的基本问题 1.0学时
第9节 识别非正则语言 2.2学时
第三章 上下文无关语言与下推自动机 姚刚
第1节 上下文无关文法 1.2学时
第2节 分析和二义性 0.8学时
第3节 上下文无关文法的化简 2.2学时
第4节 两个重要的范式 0.6学时
第5节 上下文无关文法的成员资格判定算法 1.2学时
第6节 非确定型下推自动机 1.5学时
第7节 下推自动机与上下文无关语言 2.0学时
第8节 确定型下推自动机和确定型上下文无关语言的文法 1.0学时
第9节 两个泵引理 1.2学时
第10节 上下文无关语言的封闭性质和判定算法 0.8学时
第四章 图灵机与递归可枚举语言 姚刚
第1节 标准图灵机 2.0学时
第2节 完成复杂任务的组合图灵机 0.6学时
第3节 图灵论题 0.2学时
第4节 图灵机的其他模型 1.4学时
第5节 非确定型图灵机 0.3学时
第6节 通用图灵机 0.7学时
第7节 线性有界自动机 0.4学时
第8节 递归语言和递归可枚举语言 0.9学时
第9节 无限制文法 1.0学时
第10节 上下文相关文法和语言 0.8学时
第11节 乔姆斯基层次结构 0.2学时
第五章 算法计算的限制与量子自动机 姚刚
第1节 图灵机所不能解决的问题 1.0学时
第2节 递归可枚举语言的不可判定问题 0.5学时
第3节 上下文无关语言的不可判定问题 0.5学时
第4节 量子有限自动机 0.4学时
第5节 量子下推自动机 0.3学时
第6节 量子图灵机 0.3学时
第六章 作业讲解 姚刚
第1节 作业讲解 1.0学时

姚刚，中国科学院信息工程研究所信息副研究员，是自动机方面的专家。在博士阶段，师从中国科学院软件研究所的陶仁骥研究员，自动机领域的著名专家，掌握了扎实的自动机理论基础，培养了严谨的工作作风。毕业以后，姚刚副研究员长期从事有限自动机理论和现代密码学方面的研究，在自动机理论方面发表了多篇文章。
姚刚副研究员自2007年起在中国科学院研究生院讲授《形式语言与自动机理论》课程，积累了丰富的教学经验。在教学工作中，热忱教学事业，严格要求自己，认真完成工作，履行岗位职责，取得了较好的成绩。