《形式语言与自动机》课程教学大纲

《《形式语言与自动机》课程教学大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《形式语言与自动机》课程教学大纲一、课程基本信息中文名称：形式语言与有限自动机英文名称：FormalLanguagesandAutomataTheory开课学院：计算机科学学院课程编码：S0812301学分：2总学时：36适用专业：计算机科学与技术学术硕士修读基础:《离散数学》，《数字逻辑》课程负责人：陈伟（教授）主讲教师：陈伟（教授）二、课程目的任务1.课程地位作用（课程在实现培养目标中的地位作用）《形式语言与自动机》是计算机科学的理论基础，本课程主要目的在于利用有限自动机与正则表达式的等价关系，通过表达式描述

2、问题，利用不同有限自动机类型实现解决方案，通过更一般化的上下文无关文法描述，利用下推自动机实现问题求解，培养学生描述问题、分析问题、寻求对策的创新思维模式，提高知识综合应用能力。2.课程主要内容（简述：主要内容、重点、难点等）主要内容包括：自动机理论发展历史、有限自动机的描述特点与工作方式（重点、难点）、正则表达式与语言（重点、难点）、正则语言性质、上下文无关文法与语言（重点、难点）、下推自动机、上下文无关语言的性质（重点、难点）等。3.学生应达到的基本要求本课程基本要求在于掌握有限自动机类型，有限自动机与正则表

3、达式的等价关系、正则文法性质、上下文无关文法与范式、下推自动机与上下文无关语言性质，重点在于研究应用方法。三、教学内容与学时分配（一）自动机：方法与体验（2学时）主要内容：为什么研究自动机理论，自动机理论发展历史，预备知识：字母表、串、语言、问题，主要命题证明方式。重点：预备知识（二）有限自动机（6学时）主要内容：有限自动机的非形式化描述，确定型有限自动机、非确定型有限自动机、含空转移有限自动机的描述特点与工作方式，三类自动机的等价转换方式，子集构造、空闭包概念，自动机的应用。重点：有限自动机的描述特点与工作方式

4、（三）正则表达式与语言（6学时）主要内容：正则表达式的定义，自动机FA与正则式RE的等价性及效验，RE代数规则及测试正则式RE的应用。重点：自动机FA与正则式RE的等价性（四）正则语言性质（6学时）主要内容：证明语言的非正则性，泵引理，正则语言的闭合性（闭合算子），正则语言的判定性（测试正则语言的空或成员）、自动机的状态等价与自动机最小化。重点：正则语言的闭合性与自动机最小化（五）上下文无关文法与语言（6学时）主要内容：上下文无关文法的定义，文法推导过程，上下文无关文法的语言，语法分析树和推导的等价性，语法分析器

5、及其它上下文无关文法应用，语法和语言中的歧义性及消除方法。重点：语法分析树和推导的等价性（六）下推自动机（6学时）主要内容：下推自动机的定义，下推自动机的语言，下推自动机与上下文无关文法的等价性，确定型下推自动机定义与正则语言。重点：下推自动机的工作方式与应用（七）上下文无关语言的性质（4学时）主要内容：上下文无关文法的范式，上下文无关语言的泵引理，上下文无关语言的闭合性，上下文无关语言的判定性。重点：上下文无关语言的闭合性四、考核方式与成绩评定1.考核方式：（笔试、论文、口试等）要求平时认真听课，完成四则运算计

6、算器表达式的文法描述及解释执行的大作业。2.成绩评定办法：（平时成绩、期末考试成绩……等比例）论文撰写（70％）专题讨论和答辩（30％）五、教材及主要参考书目(一)教材[1]JohnE.Hopcroft,RajeevMotwaniandJeffreyD.Ullman，IntroductiontoAutomataTheory,LanguagesandComputation,2ndedition，AddisonWesley，机械工业出版社，2004(二)参考书[1]蒋宗礼、姜守旭，形式语言与自动机理论，清华大学出版社

7、，2003年1月[2]蒋宗礼编著，形式语言与自动机理论教学参考书，清华大学出版社，2003年8月[3]J.Hopcroft&J.Ullman,自动机理论、语言和计算导引，徐美瑞译，科学出版社，1990六：其他需要说明的问题大纲执笔人：陈伟大纲审批机构：计算机科学学院教授委员会2015年8月25日