形式语言与自动机实验报告

八、实验步骤

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转移函数的储存顺序有关。故将较大可能性要用到的转移函数(始末两个状态的入度和出度较大)放在前面,有助于减小算法复杂度

报告评分:

指导教师签字:

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4