DFA确定化实验报告

DFA确定化实验报告

一、 课程设计的目的

通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。掌握子集法，即将NFA转换为与之等价的DFA的算法。 二、 课程设计的内容及要求

1. 通过设计编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。 2. 输入一个NFA 3. 输出与之等价的DFA 三、 实现原理

1、构造数据结构： 1）图的数据结构； 2）转换关系的数据结构。

2、求图的开始节点的ε-closure ，作为子集链表的头节点。然后对其ε-closure 中的每个节点，根据转换关系，求出新的子集，将新求出的子集插入到子集链表的尾部。 构造主要的数据结构：

1 / 6

DFA确定化实验报告

struct diagram {

int snum; //节点编号 move *transfer; //转换关系 diagram *next; };//图的数据结构

构造主要的数据结构： struct subset {

int snum; //节点编号，

char closure[MAX]; //该节点中包含原来 的哪些节点，也就是其ε_closure move *transfer; //来源关系 subset *next; };//子集的数据结构

构造主要的数据结构： struct move{

int point; //来自或转向哪一个节点 char input; //转向条件 move *next; };//存储来源关系

2 / 6

DFA确定化实验报告

四、 算法实现与流程

（1）读取文件中的数据，组成图的初始链表。通常，用自然语言描述这个阶段的工作是烦琐的，用子集矩阵完成这阶段工作具有直观性和简单性。以下过程将描述用子集矩阵法完成从NFA（图1）到DFA的转化：

先将图1运用子集矩阵法，通过运算得到表1。其中s表示状态，即算法描述中的自己族C；a，b表示输入字符。该阶段，可能存在没有参加运算的状态，这些状态就是不可到达的状态。不可到达过程的运算也可通过图论中的可达性进行检查。

将表1转换矩阵中的所有子集重新命名得到表2 矩阵表示形式：

3 / 6