1 《计算复杂性分析》实验指导书申进编写适用专业: 信息与计算科学怀化学院数学系 2012 年2月 2 前言通过实验,使学生加深对形式语言与自动机的基础知识的掌握。包括正则语言与有穷自动机, 上下文无关语言与下推自动机,以及图灵机的基本概念和性质。 3 目录序号实验项目名称学时实验类型实验要求 1 正则语言模块(1): 有穷自动机与正则语言. 2 验证性必修 2 正则语言模块(2): 正则表达式与正则文法. 2 验证性必修 3 上下文无关语言模块: 上下文无关语言与下推自动机 2 综合性必修 4 图灵机模块 2 综合性必修说明: 实验类型为演示性、验证性、综合性、设计性、研究性之一,实验要求为必修或选修。 4 实验一:正则语言模块( 1) :有穷自动机与正则语言实验学时: 2 实验类型:验证实验要求:必修一、实验目的 1. 了解有穷自动机的相关算法和图形化模拟; 2. 通过实验验证 NFA 和 DFA 之间的等价关系,掌握它们之间的相互转换方法。二、实验内容 1. 使用图形化模拟一台 DFA ,并分析指出它识别的语言。 2. 利用字符串模拟功能,检验两个长度超过 5 的字符串, 使得其中一个接受,一个拒绝; 3. 参考教材 52面 题, 验证 NFA 和 DFA 之间的等价关系,掌握它们之间的相互转换方法。 5 三、实验原理、方法和手段相关算法参考课程知识学习模块。四、实验组织运行要求采用以学生自主训练为主的开放模式组织教学。五、实验条件硬件: 64MB 以上的内存, 50MB 以上的硬盘空间。软件: WindowsXP 操作系统, PDF 阅读器。六、实验步骤 1. 安装形式语言和自动机课程软件, 阅读学习用户操作手册正则语言部分。 2. 完成实验内容 1 ,如下图所示: 图 DFA M= ( {1,2} , {a,b}, ?,1,{2} ). 3. 完成实验内容 2 ,如下图所示: 6 图 DFA 识别字符串 aaabb 4. 完成实验内容 3, 考虑带?的 NFA 转换成 DFA 。注意事项: (1) 该软件用@ 表示?; (2) 该软件用 a|b 表示 a,b 在同一转移箭头上,注意与书本的差别。 7 实验二:正则语言模块(2): 正则表达式与正则文法. 实验学时: 2 实验类型:验证实验要求:必修一、实验目的 1. 了解正则表达式与正则文法的定义,区别以及联系; 2. 通过实验掌握 RE 和 RG 之间的相互转换方法,以及与 NFA 和 DFA 的转换方法。二、实验内容掌握以下转换过程和方法: 1. RE E NFA ? ?(带空转移的非确定性有穷自动机) DFA ?。 2. RE E NFA DFA DFA RG ? ????最小化。 3. RG NFA ?。 4. min RG NFA DFA DFA RE ? ???。三、实验原理、方法和手段相关算法以及 RE 和 RG 的概念参考课程知识学习模块以及教材相应章节。四、实验组织运行要求采用以学生自主训练为主的开放模式组织教学。五、实验条件硬件: 64MB 以上的内存, 50MB 以上的硬盘空间。软件: WindowsXP 操作系统, PDF 阅读器。 8 六、实验步骤 1. 输入正则表达式, , * a b ab a ?,并将其转换成为相应的 NFA 。注意:(1 )在该软件中,用 a b ?表示 a b ?( 并运算)。(2 )所得结果与教材 41P 的内容有差别,找到差别所在。思考题: 51P 习题 的a 题。 2. 任意输入一个较简单的正则表达式, 转换成为等价的正则文法。 3. 任意输入一个较简单的正则文法,转换成为等价的正则表达式 9 实验三:上下文无关语言模块: 下推自动机与上下文无关文法实验学时: 2 实验类型:综合实验要求:必修一、实验目的 1 、了解上下文无关文法的概念以及性质; 2、通过实验掌握上下文无关文法的化简方法, 掌握上下文无关文法向下推自动机的转换, 二、实验内容 1 、初始化上下文无关文法; 2 、初始化下推自动机; 3 、上下文无关文法的化简; 4 、上下文无关文法向下推自动机的转换; 5、 N-PDA (以空栈方式接受语言的下推自动机)与 F-PDA (以终态方式接受语言的下推自动机)的相互转换。三、实验原理、方法和手段相关算法以及概念参考课程知识学习模块以及教材相应章节。上下文无关文法的化简方法参见相应的 PPT 。四、实验组织运行要求采用以学生自主训练为主的开放模式组织教学。五、实验条件硬件: 64MB 以上的内存, 50MB 以上的硬盘空间。 10 软件: WindowsXP 操作系统, PDF 阅读器。六、实验步骤 1. 初始化上下文无关文法,有两种方式选择:
计算复杂性实验指导书及实验报告 来自淘豆网m.daumloan.com转载请标明出处.
