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

《形式语言与自动机实验报告材料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案电子科技大学计算机学院标准实验报告（实验）课程名称形式语言与自动机电子科技大学教务处制表精彩文档实用标准文案电子科技大学实验报告学生姓名：林怡学号：2012060020023指导教师：吴婧瑾实验地点：科研楼A504实验时间：第七周周日下午一、实验室名称：计算机学院软件实验室二、实验项目名称：文法产生语言三、实验学时：6学时四、实验原理：1.文法的存储使用两种方式存储文法：程序方式与文件方式。程序方式是指文法的四元组均固化到程序内，即一个程序只对应于一个文法。文件方式是指将文法的四元组使用纯文本方式进行存

2、储，并定义好其格式。所设计的程序可处理任意的文法。2.文法的表示使用面向对象程序设计语言可描述除文法的四元式，如：采用字符数组表示其字母表和变量表，字符表示开始符号，字符串数组表示产生式组。注意产生式符号（即箭头）在ASCII字符集中没有，可采用“→”来代替。人工经常使用的，通过产生式组获得其它三元式的方式不可取，因为需要约定哪些是字母、哪些是变量，工作量很大，反而使其表示更复杂。3.句子的产生根据给定的长度产生不大于该长度的所有串。精彩文档实用标准文案两种文法存储方式均需要注意不同产生式可能有相同的左部，如S->

3、a与S->aS。要生成所有句子则不同的产生式均需要使用，因此需要一个数组（或队列、栈）来存储当前产生的句型。五、实验目的1.掌握文法的表示方法；2.理解文法产生语言的过程；3.理解有穷文法可以产生无穷语言。六、实验内容1.使用两种方式存储文法。2.使用所表示文法产生所有长度不大于N的串。七、实验器材（设备、元器件）：PC微机一台八、实验步骤给定文法G1:S->a,S->aS与G2:S->ab,S->aSb（可替换为其它稍复杂的文法）。进行如下设计：1.设计程序表示的文法G1与G2及其推导句子的方式，并与手工运行结果

4、进行对比；2.设计文法的存储格式。用4行文本表示四元式：第一行为开始状态S，第二行为终极符，第三行为产生式，第四行为非终极符；3.将文法从文件读入内存；4.对于给定的字符串长度上限，获得所有的句子；5.进行文法文件的合法性判定（如产生式中出现了既非字母，又非变量的符号）。九、实验数据及结果分析1.当输入字符串长度为N=3时，输出文件result.txt中共有三行字符串，分别为ab,aabb,aaabbb；2.当输入字符串长度为N=5时，输出文件result.txt中共有五行字符串，分别为ab,aabb,aaabbb

5、,aaaabbbb,aaaaabbbbb；精彩文档实用标准文案图一运行程序并输入字符串长度图二文件输出结果十、实验结论1.文法需要用四元式来表示；2.文法的存储方式不影响文法本身。十一、总结及心得体会通过本实验的练习，熟悉了文法的构造方法，对文法的作用有进一步理解；对抽象模型的实现方式有了整体的了解，进一步提高了程序设计技术水平。十二、对本实验过程及方法、手段的改进建议1、由于本实验给定的文法比较简单，产生式的右边只包含一个非终极符，所以对于包含多个非终极符形如S->ABab,AB->a,B->b的文法不能很好的处

6、理；2、实验中采用了类似深度优先搜索的策略，对于文法：精彩文档实用标准文案S->ab,S->aSb，S->Aa,A->a若给定字符串长度N=5，输出文本中将只有形如aaabbb的结果输出，而不会有由产生式S->Aa以及A->a所推导出的句子。所以可以把实验的要求改为给定文法能推导出的句子的长度，而不是输出文本中所有字符串的长度。报告评分：指导教师签字：精彩文档实用标准文案电子科技大学实验报告学生姓名：林怡学号：2012060020023指导教师：吴婧瑾实验地点：科研楼A504实验时间：第八周周日下午一、实验室名称：

7、计算机学院软件实验室二、实验项目名称：DFA对句子的识别三、实验学时：3学时四、实验原理DFA对句子的线性识别。五、实验目的1.加深对DFA原理的理解。2.学习使用Java进行算法的实现。3.掌握一定的图形编程。六、实验内容理解DFA的工作原理，进行如下几个方面的设计与实现：1设计固定DFA。即将DFA使用if-then-else，以及switch-case和for循环的方式表示。一个函数只能表示一个DFA，而整个的程序只围绕该DFA进行。2设计文件形式存储DFA。设计文件格式；进行DFA的动态生成；使用一组字符串

8、对所生成DFA的有效性和正确性进行验证。3图形化的显示。使用Java的图形模块进行结果的显示。七、实验器材（设备、元器件）PC微机一台精彩文档实用标准文案八、实验步骤1.设计一个简单的固定DFA，观察一个字符串使其达到的状态序列，并与手工运行结果进行对比。2.设计DFA的存储格式。文本共五行，第一行为DFA所能接受的字符，第二行为DFA的所有状态，第三行为D