编译原理实验2——自动机的确定化和最小化

本文主要是介绍编译原理实验2——自动机的确定化和最小化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

（前言：这个代码的产生真的是非常非常曲折。。。。
因为退役之后没事儿干，打算好好折腾ubuntu玩玩，结果装系统的时候把win装崩了，作业还没备份直接全没了。。
我重写的时候真的是眼里全是泪水。。。
后来实验报告写好了之后，又萌萌哒地没有备份，又留在机房一次= =
后来又是重写啊啊啊啊啊啊啊啊啊啊啊！）
使用说明：
调用NFA中的init函数可以对数组进行初始化。
调用NFA中的read函数可以将数据读入进来。
调用NFA中的check函数可以判断该结构为DFAor NFA。
调用NFA中的ChangeToDFA函数可以将该自动机对应的DFA输出出来。
调用DFA中的output可以输出对应的DFA
调用DFA中的 GetMinDFA可以输出对应的最小化的自动机。数据格式：
首先两个整数n,m，代表有n个状态m条转移。
接下来m行数，每一行有两个整数u,v和一个字符c，代表u可以通过c转移到v去。（用~代表空符号）
接下来一个数s代表起始状态。
接下来一个数Tcnt代表接收状态的个数。
接下来Tcnt个数代表接收状态的具体标号。
（状态编号为0--n- 1）样例：
3 7
0 2 0
0 0 1
1 0 0
1 1 0
2 0 0
2 1 1
2 2 0
0
1
2DFA中output的输出格式：
如果DFA中的状态有x个，转移字符有c个，那么接下来有x行
第i行为i：，接下来c个字符分别代表第i个状态接收第j个字符后转移到的状态，-1为无对应状态

代码如下：

#include<iostream>
#include<queue>
#include<iomanip>
#include<map>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
const int M = 1005;
const int CSIZE = 26;
struct DFA{/*{{{*/struct Node{int x,y,id;Node(){}Node(int x,int y,int id):x(x),y(y),id(id){}bool operator < (const Node &a)const{if(x != a.x) return x < a.x;return y < a.y;}bool operator == (const Node &a)const{return x == a.x && y == a.y;}};int ch[N][CSIZE];int cnt,C;bool accept[N];void init(){cnt = 0;memset(ch,-1,sizeof(ch));memset(accept,0,sizeof(accept));}

这篇关于编译原理实验2——自动机的确定化和最小化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---