形式语言与自动机实验报告.docx
《形式语言与自动机实验报告.docx》由会员分享，可在线阅读，更多相关《形式语言与自动机实验报告.docx（13页珍藏版）》请在冰点文库上搜索。
形式语言与自动机实验报告
电子科技大学计算机学院
标准实验报告
（实验）课程名称形式语言与自动机
电子科技大学教务处制表
电子科技大学
实验报告
学生姓名：
林怡学号：
23指导教师：
吴婧瑾
实验地点：
科研楼A504实验时间：
第七周周日下午
一、实验室名称：
计算机学院软件实验室
二、实验项目名称：
文法产生语言
三、实验学时：
6学时
四、实验原理：
1.文法的存储
使用两种方式存储文法：
程序方式与文件方式。
程序方式是指文法的四元组均固化到程序内，即一个程序只对应于一个文法。
文件方式是指将文法的四元组使用纯文本方式进行存储，并定义好其格式。
所设计的程序可处理任意的文法。
2.文法的表示
使用面向对象程序设计语言可描述除文法的四元式，如：
采用字符数组表示其字母表和变量表，字符表示开始符号，字符串数组表示产生式组。
注意产生式符号（即箭头）在ASCII字符集中没有，可采用“→”来代替。
人工经常使用的，通过产生式组获得其它三元式的方式不可取，因为需要约定哪些是字母、哪些是变量，工作量很大，反而使其表示更复杂。
3.句子的产生
根据给定的长度产生不大于该长度的所有串。
两种文法存储方式均需要注意不同产生式可能有相同的左部，如S->a与S->aS。
要生成所有句子则不同的产生式均需要使用，因此需要一个数组（或队列、栈）来存储当前产生的句型。
五、实验目的
1.掌握文法的表示方法；
2.理解文法产生语言的过程；
3.理解有穷文法可以产生无穷语言。
六、实验内容
1.使用两种方式存储文法。
2.使用所表示文法产生所有长度不大于N的串。
七、实验器材（设备、元器件）：
PC微机一台
八、实验步骤
给定文法G1:
S->a,S->aS与G2:
S->ab,S->aSb（可替换为其它稍复杂的文法）。
进行如下设计：
1.设计程序表示的文法G1与G2及其推导句子的方式，并与手工运行结果进行对比；
2.设计文法的存储格式。
用4行文本表示四元式：
第一行为开始状态S，第二行为终极符，第三行为产生式，第四行为非终极符；
3.将文法从文件读入内存；
4.对于给定的字符串长度上限，获得所有的句子；
5.进行文法文件的合法性判定（如产生式中出现了既非字母，又非变量的符号）。
九、实验数据及结果分析
1.当输入字符串长度为N=3时，输出文件result.txt中共有三行字符串，分
别为ab,aabb,aaabbb；
2.当输入字符串长度为N=5时，输出文件result.txt中共有五行字符串，分
别为ab,aabb,aaabbb,aaaabbbb,aaaaabbbbb；
图一运行程序并输入字符串长度
图二文件输出结果
十、实验结论
1.文法需要用四元式来表示；
2.文法的存储方式不影响文法本身。
十一、总结及心得体会
通过本实验的练习，熟悉了文法的构造方法，对文法的作用有进一步理解；对抽象模型的实现方式有了整体的了解，进一步提高了程序设计技术水平。
十二、对本实验过程及方法、手段的改进建议
1、由于本实验给定的文法比较简单，产生式的右边只包含一个非终极符，
所以对于包含多个非终极符形如S->ABab,AB->a,B->b的文法不能很好的处理；
2、实验中采用了类似深度优先搜索的策略，对于文法：
S->ab,S->aSb，S->Aa,A->a
若给定字符串长度N=5，输出文本中将只有形如aaabbb的结果输出，而不会有由产生式S->Aa以及A->a所推导出的句子。
所以可以把实验的要求改为给定文法能推导出的句子的长度，而不是输出文本中所有字符串的长度。
报告评分：
指导教师签字：
电子科技大学
实验报告
学生姓名：
林怡学号：
23指导教师：
吴婧瑾
实验地点：
科研楼A504实验时间：
第八周周日下午
一、实验室名称：
计算机学院软件实验室
二、实验项目名称：
DFA对句子的识别
三、实验学时：
3学时
四、实验原理
DFA对句子的线性识别。
五、实验目的
1.加深对DFA原理的理解。
2.学习使用Java进行算法的实现。
3.掌握一定的图形编程。
六、实验内容
理解DFA的工作原理，进行如下几个方面的设计与实现：
1设计固定DFA。
即将DFA使用if-then-else，以及switch-case和for循环的方式表示。
一个函数只能表示一个DFA，而整个的程序只围绕该DFA进行。
2设计文件形式存储DFA。
设计文件格式；进行DFA的动态生成；使用一组字符串对所生成DFA的有效性和正确性进行验证。
3图形化的显示。
使用Java的图形模块进行结果的显示。
七、实验器材（设备、元器件）
PC微机一台
八、实验步骤
1.设计一个简单的固定DFA，观察一个字符串使其达到的状态序列，并与手工运行结果进行对比。
2.设计DFA的存储格式。
文本共五行，第一行为DFA所能接受的字符，第二行为DFA的所有状态，第三行为DFA的状态转移函数（形如P0_0_P1）其含义为状态P0接受字符0到达状态P1，第四行为DFA的开始状态，最后一行为DFA的终止状态（可能有多个）；
3.将DFA从文件读入内存，并使用对象进行状态的合适表示。
4.对于给定的字符串，跟踪所经过的状态序列。
九、实验数据及结果分析
图1DFA状态转移图
图2程序运行结果图
十、实验结论
通过测试数据，基本验证了算法实现的正确性。
十一、总结及心得体会
通过本实验的练习，熟悉了DFA的基本工作原理，对使用DFA进行构造有了直观的认识；对实现过程中的困难有了较深的体会。
十二、对本实验过程及方法、手段的改进建议
1、本实验中由于DFA只有一个终止状态，所以可以进一步考虑有多个终止
状态的情况；
2、同样，该DFA的状态转移函数也仅限于一个状态与另一个状态之间的转
移，对于多个状态集之间的转移情况也应作考虑。
报告评分：
指导教师签字：
电子科技大学
实验报告
学生姓名：
林怡学号：
23指导教师：
吴婧瑾
实验地点：
科研楼A504实验时间：
第九周周日下午
一、实验室名称：
计算机学院软件实验室
二、实验项目名称：
NFA对句子的识别
三、实验学时：
3学时
四、实验原理
NFA对句子的非线性识别。
五、实验目的
1.加深对NFA原理的理解。
2.学习使用Java进行算法的实现。
3.进一步掌握图形编程。
六、实验内容
理解NFA的工作原理，进行如下几个方面的设计与实现：
1设计固定NFA与图形文件形式存储NFA。
2使用NFA对字符串进行判断。
3图形化的显示。
本内容属于扩展要求。
最好能进行类似单步跟踪的显示，以便学生直观地理解多条路径的产生/消亡。
七、实验器材（设备、元器件）
PC微机一台
八、实验步骤
1.设计NFA的存储格式。
文本共五行，第一行为NFA所能接受的字符，第二行为NFA的所有状态，第三行为NFA的状态转移函数（形如P0_0_P1）其含义为状态P0接受字符0到达状态P1，第四行为NFA的开始状态，最后一行为NFA的终止状态（可能有多个）；
2.将NFA从文件读入内存，并使用对象进行状态的合适表示。
3.对于给定的字符串，跟踪所经过的状态序列。
经过的状态序列。
初始状态下，只有一个活动状态，即开始状态。
读入一个字符后，由于NFA的不确定性，可能导致有多个活动状态。
随着字符的不断读入，某些活动状态的下一个状态既可以有多个，也可以一个也没有。
如果字符串读完时活动状态集合包含了某些终止状态，则说明字符串被该NFA接受。
九、实验数据及结果分析
图1NFA状态转移图
图2程序运行结果图
十、实验结论
通过测试数据，基本验证了算法实现的正确性。
十一、总结及心得体会
根据本实验，理解了NFA的实际工作原理。
实际上，对于一个字符串，由于处理过程中可能同时存在多个活动状态，其所耗费时间相当多。
十二、对本实验过程及方法、手段的改进建议
本实验中的NFA为不带空移动的NFA，可以进一步考虑带空移动的ε-NFA如何实现。
报告评分：
指导教师签字：
电子科技大学
实验报告
学生姓名：
林怡学号：
23指导教师：
吴婧瑾
实验地点：
科研楼A504实验时间：
第十周周日下午
一、实验室名称：
计算机学院软件实验室
二、实验项目名称：
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是否等价。
同时根据手工转换的方式检查自动转换程序是否正确。
九、实验数据及结果分析
图1程序运行结果图
图2生成的DFA文件
将文件dfa.txt的内容复制到实验二DFA的程序目录下，执行结果如图：
图三DFA程序检验图
十、实验结论
通过测试数据，基本验证了算法实现的正确性。
十一、总结及心得体会
根据本实验，进一步理解了NFA与DFA的等价性。
在NFA转换为DFA时，如果某些状态下无输入，可以在DFA中增加陷阱状态来表示该情况下的状态转移函数。
十二、对本实验过程及方法、手段的改进建议
1、本实验中的NFA状态转移函数较为简单，不存在同一输入下转向多个状态
的情况，所以DFA不用考虑状态列表。
可以设计更为复杂的NFA并尝试将其转换为DFA。
2、本实验对于NFA的文件存储形式还不够灵活，对于NFA的状态转移函数，
如果某状态下对某个输入没有在图上反映，也必须将其以类似P1_0_$的形式写入文本，其中$代表P1状态下读入字符0后的状态为空集∅。
报告评分：
指导教师签字：
升级会员 