课设：NFA确定化和最小化程序的设计与实现（html+css+js实现）

电玩女神 2024-05-23 18:49 33阅读 0赞

#### 文章目录 ####

*  问题描述
 *  待解决问题
 *   *  1、如何存储NFA或者是DFA
     *  2、NFA多初态问题
     *  3、子集化过程思路
     *  4、分割法过程思路
 *  使用方法：
 *  下载链接

--------------------

## 问题描述 ##

NFA确定化和最小化程序的设计与实现（参考教材3.4节）  
目的：设计一个应用程序，将给定义的任意一个NFA自动转化为DFA，并对DAF最小化。使学生能够了解和掌握NFA自动转化为DAF和最小化的过程，理解和掌握自动机的相关理论和技术方法。  
要求：  
(1)通过文件读入或者窗口提示输入一个NFA，以状态转换图或者表格形式呈现NFA；  
(2)给出采用子集法将NFA转为DFA的计算过程，以状态转换图或者表格形式呈现得到的DFA；  
(3)给出采用分割法将DFA最小化的计算过程，以状态转换图或者表格形式呈现化简之后的DFA；  
(4)呈现的NFA或者DFA需要指出开始状态和终止状态。

![在这里插入图片描述][5d1d0284e41040a3802773386bad9cf6.png]

--------------------

## 待解决问题 ##

### 1、如何存储NFA或者是DFA ###

由于我不太清楚能否使用js实现图形绘制，所以，首先能确定的是，选择***表格的方式呈现NFA和DFA***。  
为了避免处理矩阵和呈现矩阵之间需要处理产生的麻烦，所以***NFA和DFA处理的时候也采用矩阵的表示，也就是表格***。  
但是表格方式呈现的NFA与DFA***缺少***对应状态应该属于的‘***属性***’，是初始状态，终止状态，还是普通的状态，这都是***需要呈现出来的数据***。  
因此对，矩阵表达做了一些修改，***增加state状态，1做终态，-1做初态，0做普通状态***。  
继而考虑到***无法呈现ε弧线***，因此又***增加一个ε符号***。

![在这里插入图片描述][32304a4dbb3c460d993cc50aa0cb68fd.png]

***除了表头***以外的单元格，***其他的单元格都存在出现多种数据的情况***，因此每个单元格内的数据需要用***数组存储***，考虑到某一状态针对指定符号做出的move动作指向的状态是个集合，因此，如果使用数组存储这些数据，***需要考虑到数据的唯一性***。

js中存在内置的对象Set，也就是集合，集合中的数据都是唯一的，可以便利这种存储。

因此可以确定矩阵的数据结构，整体是二维矩阵，除表头以外的矩阵内的每一元素都是一个Set集合，需要避免这个集合出现集合嵌套的问题。

继而考虑到，如何从文件中读取NFA的数据。

### 2、NFA多初态问题 ###

检测state状态，将所有出现-1的行合并。

### 3、子集化过程思路 ###

使用子集化来对NFA进行确定化的过程，在一开始，需要对初态求ε闭包，然后将其对各个符号求move，如果move之后的结果没有出现过，就需要对其再重复对各个符号求move的过程。

如果你对这个感知敏感一点的话，是否出现过其实是个判定条件，重复求move直到出现的状态都出现过就是递归的体现。

若是我的代码，我使用了determinizationContinue这个函数充当这个不断递归的过程，init和end只是做一些必要的准备工作。

### 4、分割法过程思路 ###

在一开始，需要根据终态和非终态来划分两个集合，这个很容易做到，根据state的数据，分别做出两个set集合，然后将这两个集合再塞入一个大的集合就行。

而后的思路很类似于子集化过程中的递归求解。  
这边创建一个旧的状态集合，保留使用分割法前的状态集合，不做改动  
创建一个新的状态集合复制一遍旧的状态集合，然后保存分割一次后的状态集合（改动这里）。  
如果这两个状态集合保持一致，那么就说明分割完成，无需继续递归求解，不一致就继续调用函数求解。

这一部分在我的代码中体现在minimizationContinue函数之中。

分割法如何比较，先复制一遍矩阵。  
接着对这个矩阵的每一行的状态求move，判断move求解的结果，这个状态属于当前已经有的状态集合里的哪个，随后将move结果换成状态集合的字符串形式。这样属于同一状态集合的不同状态就有了共同之处，在比较的时候不会被分开。  
对所有符号对应的单元格，做出上面的操作修改矩阵之后，合并所有的符号列，接着只比较这一列就好了。相同状态集合中的状态，如果对应的这一列出现不同，就分成不同的状态集合。

--------------------

## 使用方法： ##

打开index.html文件，选择同目录下的test.xlsx文件即可。

--------------------

## 下载链接 ##

参考链接1：[学校的编译原理课设成果][Link 1]

[5d1d0284e41040a3802773386bad9cf6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/23/5201d7a2744c42f9bba37ea2d3ef5daa.png
[32304a4dbb3c460d993cc50aa0cb68fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/23/20340aa801ed4d0f8c316dd5bfc9b8e0.png
[Link 1]: https://download.csdn.net/download/Aer_7z/88746021