计算复杂性实验指导书及实验报告.doc

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