形式语言与自动机实验课程教学大纲.doc.doc

XX课程教学大纲 PAGE 2 PAGE 2 附件三：实验课程教学大纲基本格式 形式语言与自动机实验课程教学大纲 课程名称：形式语言与自动机课程编码：英文名称：Formal Languages and Automata学 时：16其中必做：16学 分：0.5开课学期：第6学期适用专业：计算机科学与技术课程类别：专业课课程性质：选修先修课程：计算机导论与程序设计，数据结构，离散数学高级程序设计语言、数据结构和算法、离散数学一、课程性质及任务 形式语言、自动机、可计算性和相关方面内容构成的计算理论，是计算机科学理论的基础内容之一。学习、研究这些内容，不仅为进一步学习、研究计算机科学所必需，而且对增强形式化能力和推理能力有重要作用本课程含有有关正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识，涉及到计算机学科方法论中所包含的三个学科形态。其内容特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性。从而培养学生的形式化描述和抽象思维能力，使学生了解和初步掌握“问题、形式化、自动化(计算机化)”的解题思路。 二、课程的教学要求 形式语言与自动机给出了对一类基本问题的抽象的基本描述和计算模型，展示了一个典型问题求解的基本思路和方法，本实验课要求学生通过实验，理解并掌握正则语言、上下文无关语言的文法、识别模型和图灵机的基本原理，并能运用这些方法解决实际问题。 三、实验项目与学时分配 序号项目内容提要学时性质要求1有穷状态自动机（FA）首先构造一个FA，并编程实现FA的过程，然后输入字符串，测试FA的功能2验证必做2词法分析设计一个文法，并编程实现一个词法分析器，能判别一个标识符是否为合法的C语言标识符。2设计必做3DFA设计模仿平板电脑的界面操作功能，实现界面状态转换。2综合必做4正则表达式与FA转换器根据正则表达式到FA的等价变化方法设计算法并编程实现将一个正则表达式转换为相应的FA。2验证必做5DFA的极小化算法对给定的DFA，实现极小化算法，输出其可区分状态表2验证必做6正则语言判定算法1设计一个算法，判定一个DFA M所接受的语言L（M）是否为空。2设计必做7上下文无关文法化简构造算法，删除CFG中的无用符号2设计必做8判断字符串是否为语言的句子构造一个算法，对任意一个字符串s和CNF G，判断其是否为L(G)的句子。2综合必做9拓扑排序实现有向无环图的识别及节点的拓扑排序2设计选做10确定的有穷状态自动机（DFA）首先构造一个DFA，并编程实现DFA的过程，然后输入字符串，测试DFA的功能2验证选做11词法分析设计一个文法，并编程实现一个词法分析器，能判别一个标识符是否为合法的C语言保留字（或保留字子集）。4设计选做12状态对关联链表构造算法设计一个算法，实现构造DFA中任意状态对的关联链表2设计选做13正则语言判定算法2设计一个算法，判定一个DFA M所接受的语言L（M）是否为无穷。2设计选做14上下文无关文法识别构造算法，对任意CFG，判断L(G)是否为空4综合选做15图灵机构造构造图灵机TM M，对于任意非负整数n,m，M能计算n+m.4综合选做16下推机设计构造一个下推机PDA，实现子程序的调用与返回。4创新选做注：项目性质：演示、验证、综合、设计、创新 项目要求：必做、选做 四、考核及成绩评定 1、考核方式：操作 2、考核标准及比例：预习报告20%、设计方案20%、系统调试30%、实验报告30% 五、主要教材、参考书 HYPERLINK /Search?book=ykeyword=吴哲辉，吴振寰 \t _blank吴哲辉 吴振寰.《形式语言与自动机理论》.北京：HYPERLINK /publish/机械工业出版社_1.html \t _blank机械工业出版社.2007年 陈有祺.《形式语言与自动机》. 北京：HYPERLINK /publish/机械工业出版社_1.html \t _blank机械工业出版社.2008年 HYPERLINK /ProductList.do?Author=蒋宗礼 \t _blank蒋宗礼 HYPERLINK /ProductList.do?Author=姜守旭 \t _blank姜守旭.《形式语言与自动机（第二版）》.北京：HYPERLINK /publish/机械工业出版社_1.html \t _blank清