编译实验三精选..doc
19页
实验三（一） NFA DFA（2 小时）一 . 问题描述NFA DFA 1. 实验目的： 学会编程实现子集构造法2. 实验任务：存储NFA与DFA，编程实现子集构造法将 NFA转换成DFA3. 实验内容：（1）确定 NFA 与 DFA 的存储格式，为 3 个以上测试 NFA 准备好存储文件2）用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序3）经测试无 误测试不易可求出 NFA与DFA的语言集合的某个子集（如长度小于某个 N），再证实两个语言集合完全相同！ （ 4）测试用例参考：将下列语言用 RE 表示，再转换成 NFA 使用：（a） 以a开头和结尾的小字字母串； a （a|b|…|z）*a | a（b） 不包含三个连续的 b 的，由字母 a 与 b 组成的字符串； （ | b | bb） （a | ab | abb）*（c） （aa|b）*（a|bb）*二．算法描述1. NFA 的输入：分别输入 NFA 的“字符集”、“状态集”、“开始状态”、“接受状态集” 、“状态转换表” 等内容，并保存在设定的变量中2. NFA 的存储与读写：将上述 NFA 的五元组保存在一个文本文件中。
存储格式如下所示 （以下图中 NFA 为例）：2 // 字符集中的字符个数 （以下两行也可合并成一行 ）a b // 以空格分隔的字符集4 // 状态个数 ( 以下两行也可合并成一行 )1 2 3 4 // 状态编号若约定总是用从 1 开始的连续数字表示，则此行可省略1 // 开始状态的编号若约定为 1，则此行可省略1 // 结束状态个数若约定为 1，则此行可省略3 // 结束状态的编号3 2 1 // 状态 1 的所有出去的转换按字符集中的字符顺序给出，并在最左边加上一列 关于 的转换 -1 表示出错状态多个状态用逗号分隔1 1 -1-1 3 4-1 -1 3NFA 中的各种信息根据3. 基本算法描述 存储格式如上所示，程序开始时，从文件中读取数据以获得 子集构造法，构造相应的函数子集构造法伪代码如下：初始时,& -closure(SO)是Dstates中唯一的状态且未被标记 while Dstates 中存在一个未标记的状态 T do begin 标记 T;for 每个输入符号 a do beginU := & -closure ( move (T, a) );if U 没在 Dstates 中 then将 U 作为一个未被标记的状态添加到 Dstates.Dtran [ T, a ] := Uendend& -closure 的计算将 T 中所有状态压入栈 stack; 将& -closure (T) 初始化为 T;while stack 不空 do begin将栈顶元素t弹出栈；for每个这样的状态 u:从t到u有一条标记为 &的边doif u 不在& -closure ( T ) 中 do begin将 u 添加到& -closure ( T )；将u压入栈stack中endend子集构造法的流程图:实验三（二）DFA化简（2小时）问题描述DFA化简1. 实验目的：学会编程实现等价划分法化简 DFA。
2. 实验任务：先完善DFA，再化简DFA3•实验内容：（1） 准备3个以上测试DFA文件2） DFA手动完善状态转换映射要是满映射）（3） 用C或JAVA语言编写用等价划分法化简 DFA的程序4） 经测试无误测试不易可求出两个 DFA的语言集合的某个子集（如长度 小于某个N）,再证实两个语言集合完全相同！（5） 编写实验报告要求同实验一，不再详述算法描述1. DFA的化简得到新的DFA之后，并没有完成任务，因为通过 NFA转化成DFA不一定是最简的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最 简的DFA[12]，也就是说，NFA转化为DFA之后，还需要化简，也就是最小化2. 化简的理论基础DFA的化简是指：寻找一个状态数最少的 DFA M，使得L（ M）=L（M '）化简的方法是消去 DFA M中的多余状态（或无用状态），合并等价状态DFA中的多余状态是指这样的状态：从开始状态出发，读入任何输入串都不 能到达的那个状态；或者从这个状态没有通路到达终态两个状态S和T等价是指：如果从状态 S出发能读出某个字 W而停于终态， 从T出发也能读出同样的字 W而停于终态；反之，从T出发能读出同样的字 W而 停于终态，从S出发也能读出某个字 W而停于终态。
3. 化简的基本思想化简DFA的基本思想是指导它的状态分成一些互不相交的子集，每一个子集 中的状态都不是等价的， 不同子集中的状态可以由某个输入串来区别， 最后将不能区别的每个子集用一个状态来做代表 [13-15]，这种方法称为“分割法”具体过程是：（1 ）将M的所有状态分成两个子集一一终态集和非终态集；（2） 考察每一个子集，若发现某子集中的状态不等价， 将其划分为两个集合；（3） 重复第（2）步，继续考察已得到的每一个子集，直到没有任何一个子集 需要继续划分为止这时 DFA的状态被分成若干个互不相交的子集4 ）从每个子集中选出一个状态做代表即可得到最简的 DFA三.程序分析通过本设计所要求达到的目的是：充分理解和掌握 NFA , DFA以及NFA确定化过程的相关概念和知识，理解和掌握子集法的相关知识和应用，现在需要编程实现对输入 NFA转换成DFA输出的功能程序总框图如下：功能图如下:四.运行结果I状态转唤矩阵如H I la lb1331-匡命名t<23>=B-D-Er刖如"F，1 la 1>>I) EI E E D博中终态为.CD竜命名.
还有 DFA的 化简过程有了更好地理解经过多次试验，在正确输入相关数据的情况下，程序 能正常运行，当错误操作或输入错误数据时，程序将应错误自动关闭经过这次课程设计，也让我深刻的认识到实践才是最重要的书本只能教给 我们基础知识，要怎样运用，将那些知识真正吸收，转化为自己的智慧，只有通过实 践才能达到编译原理是一门实用性很强，对我们的专业很有帮助的科目 ，我将会继续努力，不断增加自己的知识面，把编译原理学习的更好六.附录#include
