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

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