英文译名：Formal Language and Automata
适用领域：计算机软件与理论、计算机应用技术
开课单位：计算机科学与技术学院
教学目的：形式语言和自动机理论是理论计算机科学的重要分支，在计算机科学的许多领域起着理论基础和方法论的作用，特别是对程序语言的设计、编译理论与技术、模型检测、模式识别和自然语言理解等领域起了重要促进作用。通过对本课程的学习，研究生能够从文法和识别器的角度，掌握各类文法和自动机设计的方法和技术，提高问题的形式化描述和抽象思维能力，理解并实践“问题、形式化描述、自动化（计算机化）”的解决问题过程。
预备知识或先修课程要求：离散数学或相关知识。
教学方式及学时分配：课堂授课32学时。
学时 教学内容 教学方式 2 课程概述、语言和句子的概念 授课 2 文法的形式定义、文法的构造 授课 2 文法的乔姆斯基体系、空句子 授课 2 语言的识别、有穷状态自动机 授课 2 不确定的有穷状态自动机、带空移动的有穷状态自动机 授课 2 FA是正则语言的识别器、FA的变形 授课 2 正则表达式 授课 2 正则语言等价模型的总结、正则语言的性质 授课 2 正则语言的泵引理、正则语言的封闭性 授课 2 Myhill-Nerode定理与DFA的极小化 授课 2 关于正则语言的判定算法、上下文无关文法及化简 授课 2 乔姆斯基范式、格雷巴赫方式、自嵌套文法 授课 2 下推自动机的基本定义、PDA与CFG等价 授课 2 上下文无关语言的性质、泵引理和封闭性 授课 2 上下文无关语言的判定算法、图灵机的基本概念 授课 2 图灵机的变形、几个相关的概念、课程总结 授课
教学主要内容以及对学生的要求：
教学主要内容是形式语言与自动机方面的主要理论成果和应用实例。
要求研究生系统地掌握各类文法和自动机设计的方法和技术，形成问题的形式化描述和抽象思维的能力。
内容摘要：教学内容以四类形式语言和相应的自动机为主线，讨论形式语言与自动机方面的主要理论成果和应用实例。主要包括：介绍形式语言及其相关概念，按乔姆斯基体系讨论四类形式文法。详细介绍有穷自动机的概念、各种变形及其应用；介绍正则表达式的概念，讨论各种等价变换方法，并论述正则表达式和有穷自动机的关系；对正则语言的各种表现形式加以总结，论述正则语言的各种重要性质，并重点讨论有穷自动机的极小化问题。介绍上下文无关文法的基本概念和性质，引入下推自动机的概念，并论证下推自动机和上下文无关文法的等价性。介绍图灵机的基本概念，给出它的基本模型和各种变形，用实例表明图灵机具有很强的识别能力和计算能力，并说明图灵机和0型文法的等价性。简单介绍线性有界自动机，并证明它与上下文有关文法等价性。对各语言类之间的关系做一总结。
考核方式：闭卷考试，平时作业等占一定比例（不超过30%）。
课程主要教材：形式语言与自动机理论(第2版) .蒋宗礼.清华大学出版社,2007
主要参考书目：
[1] 自动机理论、语言和计算导论(原书第3版).（美）霍普克罗夫特著.机械工业出版社，2008
[2] 计算理论导引(第2版) .(美)西普塞.机械工业出版社，2006
[3] 形式语言与自动机. 陈有祺.机械工业出版社，2008