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

附件：怀化学院形式语言与自动机课程提纲课 程 基 本 信 息课程名称形式语言与 自动机课程代码课程类型学时32 学分2 周学时2 授课对象开课系（部）及教研室计算机科学与技术课 程 目 标一、课程设置的有关说明 1. 形式语言与自动机理论对于计算机科学与技术工作者非常重 要，它是国际上计算机学科公认的本科生必修的课程，能够引导学生高 屋建瓴地面对问题，直击本质，去伪存真，去粗取精，从关键点入手以 “计算机”方式解决问题CC2001-CS 和 CCC2002 规定了开设本课程的 明确要求以前本系开设的课程是《编译原理》，从 2013 级开始，调整 为《形式语言与自动机》 用计算机进行问题求解的基本途径是，首先要用适当的数据对问题 进行抽象和形式化表示， 然后采用适当的算法对数据进行变换得到求解 结果形式语言和自动机理论给出了对一类基本问题的抽象的基本描述 和计算模型，并研究这些模型的性质和变换方法由此展示了一个典型 的问题求解的基本思想和方法另外，它还是研究算法及编译技术的理 论基础 2. 设置本课程的目的在于： （1）培养学生对求解的问题进行形式化描述和数学模型化处理的能力 （2）培养学生在思维方法上的抽象概括能力及缜密的逻辑推理能力。

3. 课程教学基本要求 本课程的先修课程是高等数学和离散数学 本课程的主要特点是抽象和形式化，既有严格的理论证明，又有很强的 构造性，给出一些基本模型、模型的建立和性质等学生除了要掌握有关正 则语言、上下文无关语言的文法、识别模型及其基本性质、图灵机的基本知 识外，更重要的是培养和提高形式化描述和抽象思维能力教学中应注意将 数学理论紧密联系计算机科学的实际 教 学 方 法讲授法，讨论法教 学 手 段多媒体 +网络技术 +黑板板书课 程 考 核考核方式笔试考试考核要求绪论，上下文无关的性质作为识记考核 下推自动机，图灵机，上下文有关语言作为理解层次考核 文法，正则表达式， 有穷自动机， 上下文无关语言作为综合分析 层次考核成绩组成作业(20%)+出勤(20%)+期末考试 (60%) 课程教学 团队姓名职称承担教学任务电子信箱负责人唐波讲师全部教学107924542@ .com 主讲教师邓绍伟讲师全部教学课程 教学 材料使用 教材《形式语言与自动机理论》 ，蒋宗礼等著，清华大学出版社主要 参考 书目《形式语言与自动机》 ，吴哲辉，机械工业出版社 《离散数学》，左孝凌等著，上海科技文献出版社 《离散数学、理论、分析、题解》 ，左孝凌等著，上海科技文献 出版社 《Discrete Mathematical Structures》 ，Bernard Kolman, 高 等教育出版社 《离散数学》，王义和著，哈尔滨工业大学出版社网络教学 资源等其 它学习材 料 （基础知识） 电 子 教 案） 或课次课题授课 周次授课 课时课 时 累 计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体系 知识要点：短语结构文法，上下文有关文法，上下文无关文法， 正则文法，左、右线性文法 5、空语句实践环节无其他需要说明的内容：无第三章有穷自动机教学目的 与要求掌握有穷状态自动机的概念，理解识别语言数学模型教学重点语言的识别，有穷自动机教学难点有穷自动机， NFA 与 DFA 的等价性教学具体 内容1、语言的识别 知识要点：有穷状态自动机的物理模型。

2、 有穷状态自动机 知识要点：定义，状态转移图，即时描述 3、不确定的有穷状态自动机 知识要点：形式定义， NFA与 DFA的等价性 4、带空移动的有穷状态自动机 知识要点：定义 5、FA是正则语言的识别器 知识要点：证明方法 6、 关系的性质实践环节无其他需要说明的内容：无第四章正则表达式教学目的与要求掌握正则表达式这一描述正则语言的有效工具教学重点正则表达式的形式定义教学难点正则表达式与 FA 等价变换的方法以及证明教学具体 内容1、 启示 知识要点：通过实例引入概念 2、 正则表达式的形式定义 知识要点：定义 3、正则表达式与 FA等价 知识要点：等价变换的方法与证明 4、 正则语言等价模型的总结实践环节无其他需要说明的内容：无第五章正则语言的性质教学目的 与要求掌握正则语言的泵引理和正则语言的判定算法，学会 DFA的极小 化教学重点DFA 的极小化以及正则语言的判定方法教学难点DFA 的极小化教学具体内容1、 正则语言的泵引理 知识要点：泵引理的应用 2、正则语言的封闭性 知识要点：相关定理 3、Myhill-Nerode定理与 DFA的极小化 知识要点： Myhill-Nerode定理， DFA的极小化。

4、关于正则语言的判定算法 知识要点：算法实践环节无其他需要说明的内容：无第六章上下文无关语言教学目的 与要求理解上下文无关文法的性质、作用，掌握该文法的化简方法教学重点二义性，自顶向下的分析和自底向上的分析教学难点文法的二义性，上下文无关文法的派生树教学具体 内容1、上下文无关语言 知识要点：上下文无关文法的派生树，二义性，自顶向下的分析 和自底向上的分析 2、上下文无关文法的化简 知识要点：方法 3、 Chomsky范式 知识要点：定义 4、 Greibach 范式 知识要点：定义 5、自嵌套文法 知识要点：定义实践环节无其他需要说明的内容：无第七章下推自动机教学目的 与要求了解和掌握下推自动机的构造及其与上下文无关文法的等价性教学重点下推自动机的基本定义教学难点PDA与 CFG 等价的等价性的证明教学具体内容1、 基本定义 知识要点：定义 2、 PDA与 CFG 等价 知识要点：等价性证明实践环节无其他需要说明的内容：无第八章上下文无关语言的性质教学目的 与要求了解 CFG产生的语言的性质， 讨论该语言是否为空、 有穷、无穷， 以及语言句子的判断问题教学重点上下文无关语言的泵引理，上下文无关语言的封闭性教学难点上下文无关语言的判断算法教学具体内容1、 上下文无关语言的泵引理 知识要点：引理的应用。

2、 上下文无关语言的封闭性 知识要点：相关定理 3、上下文无关语言的判断算法 知识要点：应用实践环节无其他需要说明的内容：无第九章图灵机教学目的 与要求了解 TM的概念、构造及其识别的语言，为算法和可计算问题的 研究提供形式化描述的工具教学重点基本图灵机，通用图灵机教学难点可计算性， p 与 np的相关问题教学具体 内容1、基本概念 知识要点：基本图灵机，图灵机是非负整数的计算模型 2、 图灵机的变形 知识要点：双向无穷带图灵机，多带图灵机，不确定图灵机，多 维图灵机 3、 通用图灵机 知识要点：应用 4、 几个相关概念 知识要点：可计算性， P与 NP的相关问题实践环节无其他需要说明的内容：无第八章上下文有关语言教学目的 与要求了解识别 CSL的装置 —线性有界自动机（ LBA ） 教学重点图灵机与短语结构文法的等价性， 线性有界自动机及其与上下文 有关文法的等价性教学难点图灵机与短语结构文法的等价性， 线性有界自动机及其与上下文 有关文法的等价性教学具体 内容1、图灵机与短语结构文法的等价性 知识要点：相关定理 2、线性有界自动机及其与上下文有关文法的等价性 知识要点：相关定理。

实践环节无其他需要说明的内容：无。