形式语言与自动机教学提纲.doc

附件： 怀化学院形式语言与自动机课程提纲 课 程 基 本 信 息 课程名称 形式语言与自动机 课程代码 课程类型 学 时 32 学 分 2 周学时 2 授课对象 开课系（部）及教研室 计算机科学与技术 课 程 目 标 课程设置的有关说明 1. 形式语言与自动机理论对于计算机科学与技术工作者非常重要，它是国际上计算机学科公认的本科生必修的课程，能够引导学生高屋建瓴地面对问题，直击本质，去伪存真，去粗取精，从关键点入手以“计算机”方式解决问题。CC2001-CS和CCC2002规定了开设本课程的明确要求。以前本系开设的课程是《编译原理》，从2013级开始，调整为《形式语言与自动机》。 用计算机进行问题求解的基本途径是，首先要用适当的数据对问题进行抽象和形式化表示，然后采用适当的算法对数据进行变换得到求解结果。形式语言和自动机理论给出了对一类基本问题的抽象的基本描述和计算模型，并研究这些模型的性质和变换方法。由此展示了一个典型的问题求解的基本思想和方法。另外，它还是研究算法及编译技术的理论基础。 2. 设置本课程的目的在于： （1）培养学生对求解的问题进行形式化描述和数学模型化处理的能力。 （2）培养学生在思维方法上的抽象概括能力及缜密的逻辑推理能力。 3. 课程教学基本要求 本课程的先修课程是高等数学和离散数学。 本课程的主要特点是抽象和形式化，既有严格的理论证明，又有很强的构造性，给出一些基本模型、模型的建立和性质等。学生除了要掌握有关正则语言、上下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识外，更重要的是培养和提高形式化描述和抽象思维能力。教学中应注意将数学理论紧密联系计算机科学的实际。 教 学 方 法 讲授法，讨论法 教 学 手 段 多媒体+网络技术+黑板板书 课 程 考 核 考核方式 笔试考试 考核要求 绪论，上下文无关的性质作为识记考核 下推自动机，图灵机，上下文有关语言作为理解层次考核 文法，正则表达式，有穷自动机，上下文无关语言作为综合分析层次考核 成绩组成 作业(20%)+出勤(20%)+期末考试(60%) 课程教学 团队 姓名 职称 承担教学任务 电子信箱 负责人 唐波 讲师 全部教学 107924542@ 主讲教师 邓绍伟 讲师 全部教学 课程教学材料 使用 教材 《形式语言与自动机理论》，蒋宗礼等著，清华大学出版社 主要 参考 书目 《形式语言与自动机》，吴哲辉，机械工业出版社 《离散数学》，左孝凌等著，上海科技文献出版社 《离散数学、理论、分析、题解》，左孝凌等著，上海科技文献出版社 《Discrete Mathematical Structures》，Bernard Kolman, 高等教育出版社 《离散数学》，王义和著，哈尔滨工业大学出版社 网络教学资源等其它学习材料 /lishuangzhe7047/article/details/7668320（基础知识） /view/c06b4a2d3169a4517723a33e.html（电子教案） /p-4032290717788.html（相关论文） 课程教学进程 教材章节 或课次 课 题 授课周次 授课课时 课时 累计 1 绪论 1 2 2 2 文法 2 2 4 3 有穷自动机 3,4 4 8 4 正则表达式 5,6 4 12 5 正则语言的性质 7,8 4 16 6 上下文无关语言 9,10 4 20 7 下推自动机 11,12 4 24 8 上下文无关语言的性质 13 2 26 9 图灵机 14 2 28 10 上下文有关语言 15,16 4 32 课程教学内容 第一章 绪论 教学目的 与要求 使学生回顾离散数学学过的基本概念和方法，为后续学习作准备。要求精讲多练。 教学重点 集合，关系，图 教学难点 二元关系，等价关系与等价类 教学具体 内容 1、集合的基础知识 知识要点：集合及其表示，集合间的关系，集合运算。 2、关系 知识要点：二元关系，等价关系与等价类，递归定义与归纳证明，关系的闭包。 3、 图 知识要点：无向图，有向图，树。 4、 语言 知识要点：语言，形式语言与自动机理论的基本概念。 5、小结 实践环节 无 其他需要说明的内容：无 第二章 文法 教学目的 与要求 掌握文法的定义、构造方法，了解文法的Chomsky体系。 教学重点 文法的形式定义，chomsky体系 教学难点 文法的形式定义 教学具体 内容 1、启示 2、形式定义 知识要点：定义，推导，归约。 3、文法的构造 知识要点：构造方法。 4、文法的Chomsky体系 知识要