形式语言与自动机实验指导书模板.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、 写出源程序清单和执行结果。
五．实验思考
经过本实验, 如何进一步理解确定与不确定的内在联系?