NFA转DFA
编译原理课程设计实验报告（小题NFA->DFA）
一．程序功能
实现NFA到DFA的转化（包括确定化、最小化）。
二．算法思想
根据子集法对NFA确定化
①假定I是M’的状态集的子集，定义I的ε闭包ε__CLOSURE(I)
为：若q在I中，则q和从q出发任意条ε弧能到达的任意状态q’都属于ε__CLOSURE(I).
②假定I是M’的状态子集，定义Ia=ε__CLOSURE(J)。其中J
是那些可以从I中某一状态结点出发经过一条a弧而到达的状态结点的全体。
③构造一张共有K+1列的表（K为变换个数）该表的首列为ε
__CLOSURE(X)。检查该行上的所有状态子集，看它们是否已出现在表的第一列，将未曾出现者填入后面空行的第一列。重复上述过程，直至出现在第I+1列上得所有状态子集都已经在第一列上出现。
DFA最小化：
将终态组和非终态组的Ik(k=a,b……)求出，若所有集合都是组集合的子集，则DFA已最小化。
三．程序结果
请将NFA引进新的初态和终态结点
请以初态为首输入NFA信息（始状态输入符号末状态），-表示输入符号为空，以#结束
例如:
1 a 2
2 a 3
3 - 4
#
注：信息数小于50条
x - 5
5 a 5
5 b 5
5 - 1
1 a
3
1 b 4
4 b 2
3 a 2
2 - 6
6 a 6
6 b 6
6 - y
#
状态中的终态为：
y
I Ia Ib
******************************************** x51 513 514
513 51326y 514
514 513 51426y
51326y 51326y 5146y
51426y 5136y 51426y
5146y 5136y 51426y
5136y 51326y 5146y
状态子集重命名
x51->0
513->1
514->2
51326y->3
51426y->4
5146y->5
5136y->6
DFA:
I Ia Ib
********************************************
0 1 2
1 3 2
2 1 4
3 3 5
4 6 4
5 6 4
6 3 5
终态为：3456
集合划分为：
{3456}
{1}
{2}
重命名为：
{0}->0
{3456}->1
{1}->2
{2}->3
I Ia Ib
********************************************
0 2 3
1 1 1
2 1 3
3 2 1
其中终态为：1
Press any key to continue
四．源代码
#include
#include
//程序中的状态，输入符号等信息用string类型
//string.find（str）从string左边开始查找第一次str出现的位置//string.erase(x,n) 删除string从X开始的N个字符
using namespace std;
#define MAX 50
string NODE;//所有结点（状态）的集合
string StartCode;
string CHANGE;//输入符号集合
int Egde;//NFA边数
struct NFA//NFA结构体
{
string start;
string inputsign;
string end;
};
struct clo//闭包结构体
{
string ltab;//不同状态结点的空闭包
string ass[MAX];//用来存放IA IB.....
};
void closure(char a,string &CAssemble,NFA p[]){//求 _闭包
int i;
for(i=0;i { if(a==p[i].start[0])//判断某终点是哪个状态的起点 if(p[i].inputsign=="-")//输入符号为空 { if(CAssemble.find(p[i].end)>CAssemble.length()) CAssemble+=p[i].end;//将状态添加到闭包的集合CAssemble中 closure(p[i].end[0],CAssemble,p);//递归调用找到起始的 _闭包} } } void sort(string &a)//对集合元素进行排序，方便之后比较是否在状态转换表中{ int i,j; char c; for(i=0;i for(j=0;j if(NODE.find(a[j])>NODE.find(a[j+1])) { c=a[j+1]; a[j+1]=a[j]; a[j]=c; } } void add(clo &a,int m,NFA p[])//求Ia { int i,j,k,l; k=a.ltab.length(); l=a.ass[m].length(); for(i=0;i for(j=0;j if((CHANGE[m]==p[j].inputsign[0])&&(a.ass[m][i]==p[j].start[0]))//检查输入符号是否为要并入的输入符号 if(a.ass[m].find(p[j].end[0])>a.ass[m].length()) a.ass[m]+=p[j].end[0]; for(i=0;i for(j=0;j if((CHANGE[m]==p[j].inputsign[0])&&(a.ltab[i]==p[j].start[0]))//避免遗漏某状态通过输入符号指向自己 if(a.ass[m].find(p[j].end[0])>a.ass[m].length()) a.ass[m]+=p[j].end; for(i=0;i<=m;i++) if(a.ass[m].length()==0) a.ass[m]+='-'; } void output(int a,int b,clo *q)//输出状态转移矩阵 { int i,j,k,n; cout<<" I "; for(i=0;i { cout<<"I"< } cout< for(i=0;i { cout<<" "< k=q[i].ltab.length(); for(j=0;j { for(n=0;n<10-k;n++) cout<<" "; k=q[i].ass[j].length(); if(q[i].ass[j].length()==0) q[i].ass[j]+='-'; cout< } cout< } } void rename(int lenth,int count,clo *q,string &EndNode)// 对状态重命名并求出终态 { int i,j,k,m; string s,enode; for(i=0;i { s=q[i].ltab; q[i].ltab.erase(); q[i].ltab='0'+i; NODE=NODE+q[i].ltab;//对状态重新命名 cout< for(j=0;j if(s.find(EndNode[j]) //d[1]=enode enode+=q[i].ltab; for(k=0;k for(m=0;m if(s==q[k].ass[m]) q[k].ass[m]=q[i].ltab; } EndNode=enode; } void min(int lenth,string d[],clo *q,int count,string &EndNode)//DFA最小化 { string s,ednode; int a=2,i,k,j,n,b,x; int flag=0; for(i=0;i { for(k=0;k { b=a; for(j=0;j { for(n=0;n { if(d[n].find(q[NODE.find(d[i][j])].ass[k]) {//NODE.find(d[0][0])=0 if(q[NODE.find(d[i][j])].ass[k].length()==0)//闭包不再状态组中 x=a;//对应第一个元素的闭包不再状态组中，n else x=n; if(!s.length())//s作为检查是否为每个集合的第一个状态，方便比较是否在状态组中 s+=x+48; else if(s[0]!=x+48) { d[a]=d[a]+d[i][j]; flag=1; d[i].erase(j,1); j--; } break; } } } if(flag) { a++; flag=0; } //cout< s.erase(); } } for(i=0;i if(d[i].length()==0) d[i]+='-'; cout< for(i=0;i { cout<<"{"< } clo *t=new clo[a]; NODE.erase(); cout< for(i=0;i { t[i].ltab='0'+i; NODE+=t[i].ltab; cout<<"{"< } for(i=0;i for(k=0;k for(j=0;j { if(d[i][0]==q[j].ltab[0]) { for(n=0;n { if(!q[j].ass[k].length()) break; else if(d[n].find(q[j].ass[k]) { t[i].ass[k]=t[n].ltab; break; } } break; } } ednode.erase(); for(i=0;i for(j=0;j if(d[i].find(EndNode[j]) EndNode=ednode; output(lenth,a,t); cout<<"其中终态为："< delete []t; } int main() { struct NFA *p=new NFA[MAX]; int i,j,m,k,lenth; int count=1; bool flag; string EndNode,s; cout<<"请将NFA引进新的初态和终态结点"< cout<<"请以初态为首输入NFA信息（始状态输入符号末状态），-表示输入符号为空，以#结束"< cout<<"例如:"< cout<<"注：信息数小于50条"< for (i=0;i { cin>>p[i].start; if(p[i].start=="#") break; cin>>p[i].inputsign>>p[i].end; } Egde=i; for(i=0;i { if(NODE.find(p[i].start)>NODE.length()) NODE=NODE+p[i].start; if(NODE.find(p[i].end)>NODE.length()) NODE=NODE+p[i].end; if((CHANGE.find(p[i].inputsign)>CHANGE.length())&&(p[i].inputsign!="-") ) CHANGE=CHANGE+p[i].inputsign; } lenth=CHANGE.length();//求得输入符号个数方便后续求IA IB..... cout<<"状态中的终态为："< cin>>EndNode; for(i=0;i if(NODE.find(EndNode[i])>NODE.length()) { cout<<"终态不在集合中，错误！"< exit(0); } struct clo *q=new clo[MAX]; q[0].ltab=p[0].start; closure(p[0].start[0],q[0].ltab,p);//从初态开始建立闭包 for(i=0;i { for(j=0;j for(m=0;m closure(q[i].ltab[j],q[i].ass[m],p); for(k=0;k { //cout< add(q[i],k,p);//调用求IA IB的函数 //cout< for(j=0;j closure(q[i].ass[k][j],q[i].ass[k],p);//求得所有IA IB后的空闭包 } for(j=0;j { sort(q[i].ass[j]); for(k=0;k { flag=operator==(q[k].ltab,q[i].ass[j]);//判断状态是否出现在状态转换表 if(flag) break; } if(!flag&&q[i].ass[j].length())//如果没出现则从此状态开始求IA IB { q[count].ltab=q[i].ass[j]; ++count; } } } output(lenth,count,q); cout<<"状态子集重命名"< NODE.erase(); rename(lenth,count,q,EndNode); cout<<"DFA:"< output(lenth,count,q); cout<<"终态为："< string *d=new string[++count]; for(i=0;i if(EndNode.find(NODE[i])>EndNode.length()) d[0]+=NODE[i]; d[1]=EndNode; // if(d[0].length()==0) // { // cout<<"该DFA已最小化："< // exit(0); // } // for(i=0;i // for(k=0;k // cout< // cout< // cout< // for(i=0;i<1;i++) // cout< min(lenth,d,q,count,EndNode); delete []p; delete []q; delete []d; return 0; } 五．程序特色 本程序将结点信息和输入状态以及闭包内容均采用string类存放，这样做的目的在于可以使用很多的库函数。例如查找元素是否在集合中就可以采用length()函数，若结果小于集合长度，说明元素在集合中。这样可以大大减少循环的次数，降低了时间复杂度。其次将NFA到DFA的转化从确定化到最小化整体实现，从而理解NFA到DFA的转化也更加完整。