形式语言与自动机课程教学大纲课程基本信息中文名称形式

1、形式语言与自动机?课程教学大纲一、课程根本信息中文名称：形式语言与有限自动机英文名称： Formal Languages and Automata Theory 开课学院：计算机科学学院课程编码： S0812301学分： 2总学时： 36适用专业：计算机科学与技术学术硕士修读根底 : ?离散数学?，?数字逻辑?课程负责人：陈伟教授主讲教师：陈伟教授二、课程目的任务1. 课程地位作用课程在实现培养目标中的地位作用?形式语言与自动机? 是计算机科学的理论根底，本课程主要目的在于利用有限自 动机与正那么表达式的等价关系， 通过表达式描述问题，利用不同有限自动机类型实现解 决方案，通过更一般化的上下文

2、无关文法描述，利用下推自动机实现问题求解，培养学 生描述问题、分析问题、寻求对策的创新思维模式，提高知识综合应用能力。2. 课程主要内容简述：主要内容、重点、难点等 主要内容包括：自动机理论开展历史、有限自动机的描述特点与工作方式重点、 难点 、正那么表达式与语言 重点、 难点 、正那么语言性质、 上下文无关文法与语言 点、难点、下推自动机、上下文无关语言的性质重点、难点等。3. 学生应到达的根本要求 本课程根本要求在于掌握有限自动机类型，有限自动机与正那么表达式的等价关系、 正那么文法性质、上下文无关文法与范式、下推自动机与上下文无关语言性质，重点在于 研究应用方法。三、教学内容与学时分配一

3、自动机：方法与体验 2 学时主要内容：为什么研究自动机理论， 自动机理论开展历史，预备知识：字母表、串、语言、 问题，主要命题证明方式。重点：预备知识二有限自动机 6 学时主要内容：有限自动机的非形式化描述，确定型有限自动机、非确定型有限自动机、含空 转移有限自动机的描述特点与工作方式，三类自动机的等价转换方式，子集构造、 空闭包概念，自动机的应用。重点：有限自动机的描述特点与工作方式三正那么表达式与语言 6 学时主要内容：正那么表达式的定义，自动机 FA与正那么式RE的等价性及效验，RE代数规那么及测试 正那么式 RE 的应用。重点：自动机 FA 与正那么式 RE 的等价性四正那么语言性质

4、6 学时主要内容： 证明语言的非正那么性，泵引理，正那么语言的闭合性闭合算子，正那么语言的判定 性测试正那么语言的空或成员、自动机的状态等价与自动机最小化。重点：正那么语言的闭合性与自动机最小化五上下文无关文法与语言 6 学时主要内容： 上下文无关文法的定义，文法推导过程，上下文无关文法的语言，语法分析树和推 导的等价性， 语法分析器及其它上下文无关文法应用，语法和语言中的歧义性及消除方 法。重点：语法分析树和推导的等价性六下推自动机 6 学时主要内容：下推自动机的定义，下推自动机的语言，下推自动机与上下文无关文法的等价性， 确定型下推自动机定义与正那么语言。重点：下推自动机的工作方式与应用七

5、上下文无关语言的性质 4 学时主要内容：上下文无关文法的范式，上下文无关语言的泵引理，上下文无关语言的闭合性，上 文无关语言的判定性。重点：上下文无关语言的闭合性 四、考核方式与成绩评定1.考核方式：笔试、论文、口试等 要求平时认真听课，完成四那么运算计算器表达式的文法描述及解释执行的大作业。2成绩评定方法：平时成绩、期末考试成绩等比例论文撰写 70 专题讨论和辩论 30 五、教材及主要参考书目一教材1 John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman ， Introduction to Automata Theory, Languages and Computation, 2nd edition ，Addison Wesley ，机械工业出版社， 2004二参考书1 蒋宗礼、姜守旭，形式语言与自动机理论，清华大学出版社， 2003 年 1 月2 蒋宗礼编著，形式语言与自动机理论教学参考书，清华大学出版社， 2003 年 8 月3 J. Hopcroft & J. Ullman