形式语言与自动机实验指导书new

形式语言与自动机实验指导书new

ID:19784047

大小:47.50 KB

页数:10页

时间:2018-10-06

形式语言与自动机实验指导书new_第1页
形式语言与自动机实验指导书new_第2页
形式语言与自动机实验指导书new_第3页
形式语言与自动机实验指导书new_第4页
形式语言与自动机实验指导书new_第5页
资源描述:

《形式语言与自动机实验指导书new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、形式语言与自动机实验指导书电子科技大学计算机学院二○○六年八月1目录实验一文法产生语言1实验二DFA对句子的识别2实验三NFA对句子的识别4实验四NFA向DFA的转化61实验一文法产生语言一.实验目的掌握文法的表示方法,理解文法产生语言的过程,理解有穷文法可以产生无穷语言。二.实验内容1.文法的存储使用两种方式存储文法:程序方式与文件方式。程序方式是指文法的四元组均固化到程序内,即一个程序只对应于一个文法。文件方式是指将文法的四元组使用纯文本方式进行存储,并定义好其格式。所设计的程序可处理任意的文法

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

3、使用,因此需要一个数组(或队列、栈)来存储当前产生的句型。三.实验要求实验前要做好充分准备,包括程序清单、调试步骤、调试方法,以及对程序结果的分析等。8四.实验报告1、程序说明。说明程序的功能、结构。2、调试说明。包括上机调试的情况、上机调试步骤、调试所遇到的问题是如何解决的,并对调试过程中的问题进行分析,对执行结果进行分析。3、写出源程序清单和执行结果。8实验二DFA对句子的识别一.实验目的1.加深对DFA工作原理的理解。2.学习程序固定DFA的编写,以及文件形式存储DFA的构造。二.实验内容理解

4、DFA的工作原理,进行如下几个方面的设计与实现:1设计固定DFA。即将DFA使用if-then-else,以及switch-case和for循环的方式表示。一个函数只能表示一个DFA,而整个的程序只围绕该DFA进行。2设计文件形式存储DFA。设计文件格式;进行DFA的动态生成;使用一组字符串对所生成DFA的有效性和正确性进行验证。3图形化的显示。本内容属于扩展要求。如果学生能使用Java或VC里的图形模块进行结果的显示无疑是非常有意义的。其中,对于固定DFA的设计解释如下:if-then-else语

5、句一般用于输入字母表只有两个字符的情况,否则应使用switch-case来判断下一个状态是什么。另外,switch-case也用于说明当前所处的状态。For循环用于控制输入字符串,对于长度为n的输入字符串,for循环体自然应执行n次。对于文件形式存储DFA的解释如下:由于DFA是动态生成的,需要使用面向对象的方法,对于k个状态的DFA,应生成相应的k个状态对象,另外,状态间的转换应该由对象间的消息传递来实现。对象间的相互引用也是必要的。认真阅读给出的部分程序代码。完善程序,上机调试运行。三.实验要求

6、实验前要做好充分准备,包括程序清单、调试步骤、调试方法。实验后要进行对程序结果的详细分析等。8四.实验报告1、程序说明。说明程序的功能、结构。2、调试说明。包括上机调试的情况、上机调试步骤、调试所遇到的问题是如何解决的,并对调试过程中的问题进行分析,对执行结果进行分析。3、写出源程序清单和执行结果。8实验三NFA对句子的识别一.实验目的1.加深对NFA工作原理的理解,特别是如何使用确定来模拟不确定。2.学习NFA的编写。二.实验内容理解NFA的工作原理,进行如下几个方面的设计与实现:1设计固定NFA

7、与图形文件形式存储NFA。2使用NFA对字符串进行判断。3图形化的显示。本内容属于扩展要求。最好能进行类似单步跟踪的显示,以便学生直观地理解多条路径的产生/消亡。其中,NFA对字符串进行判断很有意义。初始状态下,只有一个活动状态,即开始状态。读入一个字符后,由于NFA的不确定性,可能导致有多个活动状态。随着字符的不断读入,某些活动状态的下一个状态既可以有多个,也可以一个也没有。如果字符串读完时活动状态集合包含了某些终止状态,则说明字符串被该NFA接受。这一过程说明NFA对字符串的识别过程并不是线性的

8、,即:一个长度为n的字符串并不意味着它经过了n+1个状态(重复状态需要重复计数),而可能要多很多,这与NFA本身有关。对这一点的理解对于后面的NP问题的学习有着非常重要的作用。认真阅读给出的部分程序代码。完善程序,上机调试运行。三.实验要求实验前要做好充分准备,包括程序清单、调试步骤、调试方法。实验后要进行对程序结果的详细分析等。四.实验报告1、程序说明。说明程序的功能、结构。82、调试说明。包括上机调试的情况、上机调试步骤、调试所遇到的问题是如何解决的,并对调试过程

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。