内容发布更新时间 : 2024/11/9 2:10:38星期一 下面是文章的全部内容请认真阅读。

八、实验步骤

1. 设计一个简单的固定DFA，观察一个字符串使其达到的状态序列，并与手工运行结果进行对比。

2. 设计DFA的存储格式。用邻接矩阵的方式表示DFA状态间的连接，而矩阵中的元素则表示了状态转移所需要的字母。

3. 将DFA从文件读入内存，并使用对象进行状态的合适表示。 4. 对于给定的字符串，跟踪所经过的状态序列。

九、实验数据及结果分析

本实验采用的DFA接受的语言为：

L={w|w∈{0，1}*，且w必须包含110子串} 1、 输入101101，结果如下图：

2、 输入01001，结果如下图：

3、 手工验算可知，结果均正确。

十、实验结论

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

十一、总结及心得体会

通过本实验的练习，熟悉了DFA的基本工作原理，对使用DFA进行构造有了直观的认识；对实现过程中的困难有了较深的体会。

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

采用邻接矩阵的方式表示DFA状态间的连接关系很直观，但由于某些边可能对应多个权值，某些状态间无通路，故需事先定义好邻接矩阵中各类数值的具体含义，以免发生歧义。

报告评分：

指导教师签字：

电 子 科 技 大 学

实 验 报 告

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

实验地点：科A502 实验时间：2014年11月2日 一、实验室名称：计算机学院软件实验室 二、实验项目名称：NFA对句子的识别 三、实验学时：3学时 四、实验原理

NFA对句子的非线性识别。

五、实验目的

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

六、实验内容

理解NFA的工作原理，进行如下几个方面的设计与实现： 1设计固定NFA与图形文件形式存储NFA。 2使用NFA对字符串进行判断。

3图形化的显示。本内容属于扩展要求。最好能进行类似单步跟踪的显示，以便学生直观地理解多条路径的产生/消亡。

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

PC微机一台 八、实验步骤

1. 设计NFA的存储格式。用邻接矩阵的方式表示NFA状态间的连接，而矩阵中的元素则表示了状态转移所需要的字母。

2. 将NFA从文件读入内存，并使用对象进行状态的合适表示。 3. 对于给定的字符串，跟踪所经过的状态序列。

经过的状态序列。初始状态下，只有一个活动状态，即开始状态。读入一个字符后，由于NFA的不确定性，可能导致有多个活动状态。随着字符的不断读入，某些活动状态的下一个状态既可以有多个，也可以一个也没有。如果字符串读完时活动状态集合包含了某些终止状态，则说明字符串被该NFA接受。

这一点在逐步对NFA的活动状态跟踪过程中体现得非常明显。

九、实验数据及结果分析

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

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

1、输入01101，结果如下图：

2、输入100，结果如下：

3、手工验证可知结果均正确。

十、实验结论

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

十一、总结及心得体会

根据本实验，理解了NFA的实际工作原理。实际上，对于一个字符串，由于处理过程中可能同时存在多个活动状态，其所耗费时间相当多。

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

实验中对多个活动状态（路径）的处理方法是一次遍历，其算法复杂度与NFA转移函数的储存顺序有关。故将较大可能性要用到的转移函数（始末两个状态的入度和出度较大）放在前面，有助于减小算法复杂度

报告评分：

指导教师签字：