063403     形式语言与自动机                              32学时/ 2学分
英文译名：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