内容发布更新时间 : 2024/11/20 11:42:49星期一 下面是文章的全部内容请认真阅读。

DFA（确定的有穷自动机）的化简

1. 实验内容

输入一个DFA M,输出一个与之等价的最小化的DFA M’，设计并实现将NFA确定化为DFA的子集构造算法，输入非确定有限（穷）状态自动机，输出确定化的有限（穷）状态自动机 编写一个程序，将一个非确定有限自动机转换为确定有限自动机。

2. 实验设计分析

2.1 实验设计思路

首先输入边集找到状态与边的关系，然后输入终结点，这样一个没有简化的NFA图就表示出来了，然后利用求闭包的方式求move集合，画出状态转化图，重命名后进行集合划分，再次重新画出状态转换矩阵，输出简化后的DFA。

2.2 实验算法

（1）构造具有两个组的状态集合的初始划分I：接受状态组 F 和非接受状态组 Non-F。

（2）对I采用下面所述的过程来构造新的划分I-new. For I 中每个组G do Begin

当且仅当对任意输入符号a,状态s和读入a后转换到I的同一组中； /*最坏情况下，一个状态就可能成为一个组*/ 用所有新形成的小组集代替I-new中的G; end

（3）如果I-new=I，令I-final=I,再执行第（4）步，否则令I=I=new,重复步骤（2）。

（4）在划分I-final的每个状态组中选一个状态作为该组的代表。这些代表构成了化简后的DFA M＇状态。令s是一个代表状态，而且假设：在DFA M中，输入为a时有从s到t转换。令t所在组的代表是r,那么在M’中有一个从s到r的转换，标记为a。令包含s0的状态组的代表是M’的开始状态，并令M’的接受状态是那些属于F的状态所在组的代表。注意,I-final的每个组或者仅含F中的状态，或者不含F中的状态。

（5）如果M’含有死状态（即一个对所有输入符号都有刀自身的转换的非接受状态d）,则从M’中去掉它；删除从开始状态不可到达的状态；取消从任何其他状态到死状态的转换。

2.3 实验流程 1. 2. 3. 4. 5. 6.

2.4 实验的基本技术设计方案

实验中含有一些数据结构的知识，假设I是NFA M状态集K的一个子集（即I∈K），则定义ε-closure（I）为： 若Q∈I，则Q∈ε-closure（I）；

若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈ε-closure（I）。

状态集ε-closure（I）称为状态I的ε闭包。

假设NFA M＝（K，∑，F，S，Z），若I∈K，a∈∑，则定义Ia＝ε-closure（J），其中J是所有从ε-closure（I）出发，经过一条a弧而到达的状态集。

2.5 数据结构

实现的数据结构：

用链表实现DFA的构造：由结点链表和转换弧链表组成： struct node //结点的定义

{intpos;//结点在哪个组中 intnum；//结点的序号

int accept; //结点是否为接受状态 struct node *next; }NODE;

struct arc//弧的定义

{int start; //开始的顶点位置

char input; //弧上所接受的输入字符 int end; //结束的顶点位置 struct arc *next;

}ARC;

Struct groups //分组后各结点所在组的位置 {int n; //属于哪个组 int i;//在组中的位置

输入NFA各边信息（起点条件[空为*] 终点），以#结束 输入终态

求e-clouse闭包,将结点移入相应的闭包集合，并重新排序 输出状态转换矩阵，转换成DFA并重命名 执行DFA最简化

重命名DFA，输出最简化DFA状态转换矩阵

}GROUPs;

2.6 实验输入输出

在测试中，一共有0、1两个状态，它们之间的符号位a/b/*，首先定义边集并赋值，输入终态，程序会自动输出状态转换矩阵，重命名后，进行划分，再重命名，输出新的状态转换矩阵，实现DFA的简化。