形式语言与自动机实验指导书模板.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。形式语言与自动机实验指导书 电子科技大学计算机学院二六年八月目 录实验一 文法产生语言1实验二 DFA对句子的识别2实验三 NFA对句子的识别4实验四 NFA向DFA的转化6实验一 文法产生语言一实验目的掌握文法的表示方法, 理解文法产生语言的过程, 理解有穷文法能够产生无穷语言。二实验内容1. 文法的存储使用两种方式存储文法: 程序方式与文件方式。程序方式是指文法的四元组均固化到程序内, 即一个程序只对应于一个文法。文件方式是指将文法的四元组使用纯文本方式进行存储, 并定义好其格式。所设计的程序可处理任意的文法。2. 文法的表示使用面向对象程序设计语言可描述除文法的四元式, 如: 采用字符数组表示其字母表和变量表, 字符表示开始符号, 字符串数组表示产生式组。注意产生式符号( 即箭头) 在ASCII字符集中没有, 可采用”-”来代替。人工经常使用的, 经过产生式组获得其它三元式的方式不可取, 因为需要约定哪些是字母、 哪些是变量, 工作量很大, 反而使其表示更复杂。3. 句子的产生根据给定的长度产生不大于该长度的所有串。两种文法存储方式均需要注意不同产生式可能有相同的左部, 如S - a 与 S - aS。要生成所有句子则不同的产生式均需要使用, 因此需要一个数组( 或队列、 栈) 来存储当前产生的句型。三实验要求实验前要做好充分准备, 包括程序清单、 调试步骤、 调试方法, 以及对程序结果的分析等。四实验报告1、 程序说明。说明程序的功能、 结构。2、 调试说明。包括上机调试的情况、 上机调试步骤、 调试所遇到的问题是如何解决的, 并对调试过程中的问题进行分析, 对执行结果进行分析。3、 写出源程序清单和执行结果。 实验二 DFA对句子的识别一. 实验目的1. 加深对DFA工作原理的理解。2. 学习程序固定DFA的编写, 以及文件形式存储DFA的构造。二. 实验内容理解DFA的工作原理, 进行如下几个方面的设计与实现: 1 设计固定DFA。即将DFA使用if-then-else, 以及switch-case和for循环的方式表示。一个函数只能表示一个DFA, 而整个的程序只围绕该DFA进行。2 设计文件形式存储DFA。设计文件格式; 进行DFA的动态生成; 使用一组字符串对所生成DFA的有效性和正确性进行验证。3 图形化的显示。本内容属于扩展要求。如果学生能使用Java或VC里的图形模块进行结果的显示无疑是非常有意义的。其中, 对于固定DFA的设计解释如下: if-then-else语句一般用于输入字母表只有两个字符的情况, 否则应使用switch-case来判断下一个状态是什么。另外, switch-case也用于说明当前所处的状态。For循环用于控制输入字符串, 对于长度为n的输入字符串, for循环体自然应执行n次。对于文件形式存储DFA的解释如下: 由于DFA是动态生成的, 需要使用面向对象的方法, 对于k个状态的DFA, 应生成相应的k个状态对象, 另外, 状态间的转换应该由对象间的消息传递来实现。对象间的相互引用也是必要的。认真阅读给出的部分程序代码。完善程序, 上机调试运行。三实验要求实验前要做好充分准备, 包括程序清单、 调试步骤、 调试方法。实验后要进行对程序结果的详细分析等。四实验报告1、 程序说明。说明程序的功能、 结构。2、 调试说明。包括上机调试的情况、 上机调试步骤、 调试所遇到的问题是如何解决的, 并对调试过程中的问题进行分析, 对执行结果进行分析。3 写出源程序清单和执行结果。 实验三 NFA对句子的识别一. 实验目的1. 加深对NFA工作原理的理解, 特别是如何使用确定来模拟不确定。2. 学习NFA的编写。二. 实验内容理解NFA的工作原理, 进行如下几个方面的设计与实现: 1 设计固定NFA与图形文件形式存储NFA。2 使用NFA对字符串进行判断。3 图形化的显示。本内容属于扩展要求。最好能进行类似单步跟踪的显示, 以便学生直观地理解多条路径的产生/消亡。其中, NFA对字符串进行判断很有意义。初始状态下, 只有一个活动状态, 即开始状态。读入一个字符后, 由于NFA的不确定性, 可能导致有多个活动状态。随着字符的不断读入, 某些活动状态的下一个状态既能够有多个, 也能够一个也没有。如果字符串读完时活动状态集合包含了某些终止状态, 则说明字符串被该NFA接受。这一过程说明NFA对字符串的识别过程并不是线性的, 即: 一个长度为n的字符串并不意味着它经过了n + 1个状态( 重复状态需要重复计数) , 而可能要多很多, 这与NFA本身有关。对这一点的理解对于后面的NP问题的学习有着非常重要的作用。认真阅读给出的部分程序代码。完善程序, 上机调试运行。三实验要求实验前要做好充分准备, 包括程序清单、 调试步骤、 调试方法。实验后要进行对程序结果的详细分析等。四实验报告1、 程序说明。说明程序的功能、 结构。2、 调试说明。包括上机调试的情况、 上机调试步骤、 调试所遇到的问题是如何解决的, 并对调试过程中的问题进行分析, 对执行结果进行分析。3、 写出源程序清单和执行结果。 五实验思考在本实验的过程中, 是如何使用确定来描述不确定的? 实验四 NFA向DFA的转化一. 实验目的1. 理解NFA向DFA的转化的原理, 进一步理解确定与不确定的内在联系。2. 学习转换程序的编写。二. 实验内容理解NFA向DFA的转化的原理, 进行如下几个方面的设计与实现: 1 根据文件形式存储NFA获得转移函数。在实验五的基础上, NFA的状态转移函数比较容易获得。2 根据NFA状态转移函数构造相应DFA的状态转移函数。这是本实验的重点。一个有n个状态的NFA转化后的DFA最多有2n个状态, 因此表的最大长度为2n。由于多个状态是无用状态, 在转化过程中并不需要为其进行计算。如何避免无效的计算, 同时保证转换过程的正确性是本实验的难点。3 生成相应的DFA。在实验四的基础上, 这一方面的功能不会太难。但要注意终止状态的设定。认真阅读给出的部分程序代码。完善程序, 上机调试运行。三实验要求实验前要做好充分准备, 包括程序清单、 调试步骤、 调试方法。实验后要进行对程序结果的详细分析等。四实验报告1、 程序说明。说明程序的功能、 结构。2、 调试说明。包括上机调试的情况、 上机调试步骤、 调试所遇到的问题是如何解决的, 并对调试过程中的问题进行分析, 对执行结果进行分析。3、 写出源程序清单和执行结果。 五实验思考经过本实验, 如何进一步理解确定与不确定的内在联系?