内容发布更新时间 : 2024/5/10 8:30:57星期一 下面是文章的全部内容请认真阅读。

电 子 科 技 大 学

实 验 报 告

学生姓名： 学 号： 指导教师：

实验地点：科A502 实验时间：2014年11月16日 一、实验室名称：计算机学院软件实验室 二、实验项目名称：NFA向DFA的转化 三、实验学时：4学时 四、实验原理

NFA的一个状态子集可以用DFA的一个状态表示。

五、实验目的

1. 加深对NFA和DFA等价性的理解。 2. 学习使用Java进行算法的实现。 3. 进一步掌握图形编程。

六、实验内容

理解NFA向DFA的转化的原理，进行如下几个方面的设计与实现： 1据文件形式存储NFA获得转移函数。在实验五的基础上，NFA的状态转移函数比较容易获得。

2根据NFA状态转移函数构造相应DFA的状态转移函数。这是本实验的重点。一个有n个状态的NFA转化后的DFA最多有2n个状态，因此表的最大长度为2n。由于多个状态是无用状态，在转化过程中并不需要为其进行计算。如何避免无效的计算，同时保证转换过程的正确性是本实验的难点。 3生成相应的DFA。在实验四的基础上，这一方面的功能不会太难。但要注意终止状态的设定。

七、实验器材（设备、元器件）

PC微机一台 八、实验步骤

1. 设计一个方法（函数），它可以根据NFA获得其状态转移函数。 2. 设计一个方法，它可以将NFA的状态转移函数转换为DFA的状态转移函数。

3. 在上一步的基础上，设计一个方法，它可以在转换过程中尽量避免无效的计算。

4. 根据DFA的状态转移函数，进行DFA的内部表示。

5. 根据DFA的内部表示，写入相应的文件，以便下次从该文件重新读取并构建DFA。

6. 使用一组字符串，验证生成的DFA与原始的NFA是否等价。同时根据手工转换的方式检查自动转换程序是否正确。

九、实验数据及结果分析

实验中采用的NFA接受的语言为：

L={w|w∈{0，1}*，若w以0结尾，则w长度为奇数；若w以1结尾，

则w长度为偶数}

实验结果如下，手工验算可知，转化后的DFA与原NFA等价。也可用实验二和三验证两个文法对同一个输入字符串的识别结果相同。

十、实验结论

通过测试数据，基本验证了算法实现的正确性。

十一、总结及心得体会

根据本实验，进一步理解了NFA与DFA的等价性。

十二、对本实验过程及方法、手段的改进建议

可考虑直接将转化得到的DFA保存为文件，在用实验二和实验三的识别模块验证两文法的等价性。

报告评分：

指导教师签字：