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

1、电子科技大学计算机学院标准实验报告（实验）课程名称形式语言与自动机电子科技大学教务处制表技大学 报告 指导教师：吴婧瑾实验时间：第七周周日下午电子科实验学生姓名： 林怡 学号： 23实验地点： 科研楼 a504一、实验室名称： 计算机学院软件实验室二、实验项目名称： 文法产生语言三、实验学时： 6 学时四、实验原理:1. 文法的存储使用两种方式存储文法：程序方式与文件方式。程序方式是指文法的四元组均固化到程序内，即一个程序只对应于一个文法。文件方式是指将文法的四元组使用纯文本方式进行存储，并定义好其格式。所设计的程序可处理任意的文法。2. 文法的表示使用面向对象程序设计语言可描述除文法的四元式

2、， 如： 采用字符数组表示其字母表和变量表， 字符表示开始符号， 字符串数组表示产生式组。 注意产生式 符号（即箭头）在ascii字符集中没有，可采用来代替。人工经常使用的， 通过产生式组获得其它三元式的方式不可取， 因为需要约 定哪些是字母、哪些是变量，工作量很大，反而使其表示更复杂。3. 句子的产生根据给定的长度产生不大于该长度的所有串。两种文法存储方式均需要注意不同产生式可能有相同的左部， 如 s - a 与 s - as。要生成所有句子则不同的产生式均需要使用，因此需要一个数组（或队列、栈）来存储当前产生的句型。五、实验目的1. 掌握文法的表示方法；2. 理解文法产生语言的过程；3.

3、理解有穷文法可以产生无穷语言。六、实验内容1. 使用两种方式存储文法。2. 使用所表示文法产生所有长度不大于n 的串。七、实验器材（设备、元器件） ：pc微机一台八、实验步骤给定文法gi: s - a, s - as与g2: s - ab, s - asb （可替换为其它稍复杂的文法） 。进行如下设计：1. 设计程序表示的文法g1 与 g2 及其推导句子的方式，并与手工运行结果进行对比；2. 设计文法的存储格式。 用 4 行文本表示四元式： 第一行为开始状态s， 第二行为终极符，第三行为产生式，第四行为非终极符；3. 将文法从文件读入内存；4. 对于给定的字符串长度上限，获得所有的句子；5.

4、进行文法文件的合法性判定（如产生式中出现了既非字母，又非变量的符号） 。九、实验数据及结果分析1. 当输入字符串长度为n=3 时，输出文件result.txt 中共有三行字符串，分别为 ab, aabb, aaabbb ；2. 当输入字符串长度为n=5 时，输出文件result.txt 中共有五行字符串，分 别为 ab, aabb, aaabbb, aaaabbbb, aaaaabbbbb运行程序并输入字符串长度图二 文件输出结果十、实验结论1. 文法需要用四元式来表示；2. 文法的存储方式不影响文法本身。十一、总结及心得体会通过本实验的练习，熟悉了文法的构造方法，对文法的作用有进一步理解；对

5、抽象模型的实现方式有了整体的了解，进一步提高了程序设计技术水平。十二、对本实验过程及方法、手段的改进建议1、 由于本实验给定的文法比较简单，产生式的右边只包含一个非终极符，所以对于包含多个非终极符形如 s-abab,ab-a,b-b 的文法不能很好的处理；2、 实验中采用了类似深度优先搜索的策略，对于文法：s - ab, s - asb， s-aa,a-a若给定字符串长度n=5 ，输出文本中将只有形如 aaabbb 的结果输出，而不会有由产生式 s-aa 以及 a-a 所推导出的句子。所以可以把实验的要求改为给定文法能推导出的句子的长度，而不是输出文本中所有字符串的长度。报告评分：指导教师签字

6、：技大学 报告 指导教师：吴婧瑾实验时间：第八周周日下午电子科实验学生姓名： 林怡 学号： 23实验地点： 科研楼 a504一、实验室名称： 计算机学院软件实验室二、实验项目名称： dfa 对句子的识别三、实验学时： 3 学时四、实验原理dfa 对句子的线性识别。五、实验目的1. 加深对 dfa 原理的理解。2. 学习使用java进行算法的实现。3. 掌握一定的图形编程。六、实验内容理解 dfa 的工作原理，进行如下几个方面的设计与实现：1设计固定dfa。即将dfa使用if-then-else,以及switch-case和for循环的方式表示。一个函数只能表示一个dfa ，而整个的程序只围绕该

7、dfa 进行。2 设计文件形式存储dfa 。 设计文件格式； 进行 dfa 的动态生成； 使用一组字符串对所生成dfa 的有效性和正确性进行验证。3 图形化的显示。使用 java 的图形模块进行结果的显示。七、实验器材（设备、元器件）pc微机一台八、实验步骤1 .设计一个简单的固定 dfa,观察一个字符串使其达到的状态序列，并与 手工运行结果进行对比。2 .设计dfa的存储格式。文本共五行，第一行为dfa所能接受的字符，第 二行为dfa的所有状态，第三行为dfa的状态转移函数（形如p0_0_p1）其含 义为状态p0接受字符0到达状态p1,第四行为dfa的开始状态，最后一行为 dfa的终止状态（

8、可能有多个）；3 .将dfa从文件读入内存，并使用对象进行状态的合适表示。4 .对于给定的字符用，跟踪所经过的状态序列。九、实验数据及结果分析图1dfa状态转移图图2程序运行结果图通过测试数据，基本验证了算法实现的正确性。十一、总结及心得体会通过本实验的练习，熟悉了 dfa 的基本工作原理，对使用 dfa 进行构造有 了直观的认识；对实现过程中的困难有了较深的体会。十二、对本实验过程及方法、手段的改进建议1、 本实验中由于 dfa 只有一个终止状态， 所以可以进一步考虑有多个终止状态的情况；2、 同样， 该 dfa 的状态转移函数也仅限于一个状态与另一个状态之间的转移，对于多个状态集之间的转移

9、情况也应作考虑。报告评分：指导教师签字：十、实验结论技大学 报告 指导教师：吴婧瑾实验时间：第九周周日下午电子科实验学生姓名： 林怡 学号： 23实验地点： 科研楼 a504一、实验室名称： 计算机学院软件实验室二、实验项目名称： nfa 对句子的识别三、实验学时： 3 学时四、实验原理nfa 对句子的非线性识别。五、实验目的1. 加深对 nfa 原理的理解。2. 学习使用java进行算法的实现。3. 进一步掌握图形编程。六、实验内容理解 nfa 的工作原理，进行如下几个方面的设计与实现：1 设计固定 nfa 与图形文件形式存储nfa 。2 使用 nfa 对字符串进行判断。3 图形化的显示。本

10、内容属于扩展要求。最好能进行类似单步跟踪的显示，以便学生直观地理解多条路径的产生/ 消亡。七、实验器材（设备、元器件）pc微机一台八、实验步骤1 .设计nfa的存储格式。文本共五行，第一行为nfa所能接受的字符，第 二行为nfa的所有状态，第三行为nfa的状态转移函数（形如p0_0_p1）其含 义为状态p0接受字符0到达状态p1,第四行为nfa的开始状态，最后一行为nfa的终止状态（可能有多个）；2 .将nfa从文件读入内存，并使用对象进行状态的合适表示。3 .对于给定的字符用，跟踪所经过的状态序列。经过的状态序列。初始状态下，只有一个活动状态，即开始状态。读入一个 字符后，由于nfa的不确定

11、性，可能导致有多个活动状态。随着字符的不断读 入，某些活动状态的下一个状态既可以有多个， 也可以一个也没有。如果字符串 读完时活动状态集合包含了某些终止状态，则说明字符串被该nfa接受。九、实验数据及结果分析图1 nfa状态转移图程序运行结果图通过测试数据，基本验证了算法实现的正确性。十一、总结及心得体会根据本实验，理解了 nfa 的实际工作原理。实际上，对于一个字符串，由于处理过程中可能同时存在多个活动状态，其所耗费时间相当多。十二、对本实验过程及方法、手段的改进建议本实验中的nfa为不带空移动的nfa,可以进一步考虑带空移动的e -nfa如何实现。报告评分：指导教师签字：技大学 报告 指导

12、教师：吴婧瑾实验时间：第十周周日下午电子科实验学生姓名： 林怡 学号： 23实验地点： 科研楼 a504一、实验室名称： 计算机学院软件实验室二、实验项目名称： nfa 向 dfa 的转化三、实验学时： 4 学时四、实验原理nfa 的一个状态子集可以用 dfa 的一个状态表示。五、实验目的1. 加深对 nfa 和 dfa 等价性的理解。2. 学习使用java进行算法的实现。3. 进一步掌握图形编程。六、实验内容理解 nfa 向 dfa 的转化的原理，进行如下几个方面的设计与实现：1 据文件形式存储nfa 获得转移函数。在实验五的基础上， nfa 的状态转移函数比较容易获得。2根据 nfa 状态

13、转移函数构造相应dfa 的状态转移函数。 这是本实验的重点。一个有n个状态的nfa转化后的dfa最多有2n个状态，因此表的最大长度 为2n。由于多个状态是无用状态，在转化过程中并不需要为其进行计算。如 何避免无效的计算，同时保证转换过程的正确性是本实验的难点。3 生成相应的dfa 。在实验三的基础上，这一方面的功能不会太难。但要注意终止状态的设定。七、实验器材（设备、元器件）pc微机一台八、实验步骤1. 设计一个方法（函数） ，它可以根据nfa 获得其状态转移函数。2. 设计一个方法， 它可以将 nfa 的状态转移函数转换为 dfa 的状态转移函 数。3. 在上一步的基础上，设计一个方法，它可

14、以在转换过程中尽量避免无效 的计算。4. 根据dfa 的状态转移函数，进行dfa 的内部表示。5. 根据dfa 的内部表示，写入相应的文件，以便下次从该文件重新读取并构建 dfa 。6. 使用一组字符串，验证生成的dfa与原始的nfa是否等价。同时根据手 工转换的方式检查自动转换程序是否正确。九、实验数据及结果分析1 程序运行结果图图 2 生成的 dfa 文件将文件 dfa.txt 的内容复制到实验二dfa 的程序目录下，执行结果如图：图三 dfa 程序检验图十、实验结论通过测试数据，基本验证了算法实现的正确性。十一、总结及心得体会根据本实验，进一步理解了 nfa与dfa的等价性。在nfa转换为dfa时,如果某些状态下无输入，可以在dfa 中增加陷阱状态来表示该情况下的状态转移函数。十二、对本实验过