NFA到DFA的确定化及最小化

NFA转化为DFA的确定化及最小化一NFA向DFA的转换从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态.DFA使用它的状态记录在NFA读入一个输入符号后可能达到的所有状态.得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最简的DFA[12]，也就是说，NFA转化为DFA之后，还需要化简，也就是最小化。二NFA的确定化方法子集法：1．先把DFAM’中的Q’和F’置为空集；2．M’的开始状态q0’=[q0]，把[q0]置为未标记后加入到Q’中；3．如果Q’中存在未标记的状态[q1,q2,„，qi]，则对每个a∈∑定义：δ’([q1,q2,„，qi],a)=[p1,p2,„,pi]当且仅当δ({q1,q2,„，qi},a)={p1,p2,„,pi}。如果[q1,q2,„，qi]不在Q’中，则把它置为为标记后加入到Q’中；如果p1,p2,„,pi中至少有一个是M的终态，则同时把[p1,p2,„,pi]加入到F’中；然后给Q’中所有的状态都标记为止；4．重复执行（3），直到不能向Q’中加入新状态，并且Q’中所有的状态都有标记为止；5.重新命名Q’中的状态，最后获得等价的DFAM’。二、对含ε变迁的NFA的确定化：1．置Q’,F’为空集；2．令q0’=[ε_CLOSURE({q0})],并把[q0]置为未标记后加入到Q’中；3．如果Q’中存在未标记状态[q1,q2,„,qi],则对每个a∈∑定义：d‘([q1,q2,„qi],a)=[p1,p2,„,pj]当且仅当d({q1,q2,„qi},a)={r1,r2,„,rk},ε_CLOSURE({r1,r2,„,rk})={p1,p2,„,pj}。如果[p1,p2,„,pj]不在Q’中，则把它置为未标记后加入到Q’中；如果p1,p2,„,pj中至少有一个是M的终态，则同时把[p1,p2,„,pj]加入到F’中；然后给Q’中的状态[q1,q2,„,qi]加上标记；4．重复执行3，直到不能向Q’中加入新状态，并且Q’中所有的状态都有标记为止；5．重新命名Q’中的状态，然后获得等价的DFAM’三数据结构structedge{stringfirst;stringchange;stringlast;};structchan{stringltab;stringjihe[MAXS];};四源代码#includeiostream#includestring#defineMAXS100usingnamespacestd;stringNODE;//结点集合stringCHANGE;//终结符集合intN;//NFA边数structedge{stringfirst;stringchange;stringlast;};structchan{stringltab;stringjihe[MAXS];};voidkong(inta){inti;for(i=0;ia;i++)cout'';}//排序voidpaixu(string&a){inti,j;charb;for(j=0;ja.length();j++)for(i=0;ia.length();i++)if(NODE.find(a[i])NODE.find(a[i+1])){b=a[i];a[i]=a[i+1];a[i+1]=b;}}voideclouse(charc,string&he,edgeb[]){intk;for(k=0;kN;k++){if(c==b[k].first[0])if(b[k].change==*){if(he.find(b[k].last)he.length())he+=b[k].last;eclouse(b[k].last[0],he,b);}}}voidmove(chan&he,intm,edgeb[]){inti,j,k,l;k=he.ltab.length();l=he.jihe[m].length();for(i=0;ik;i++)for(j=0;jN;j++)if((CHANGE[m]==b[j].change[0])&&(he.ltab[i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])he.jihe[m].length())he.jihe[m]+=b[j].last[0];for(i=0;il;i++)for(j=0;jN;j++)if((CHANGE[m]==b[j].change[0])&&(he.jihe[m][i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])he.jihe[m].length())he.jihe[m]+=b[j].last[0];}//输出voidoutputfa(intlen,inth,chan*t){inti,j,m;coutI;for(i=0;ilen;i++)cout'I'CHANGE[i];coutendl-------------------------endl;for(i=0;ih;i++){cout''t[i].ltab;m=t[i].ltab.length();for(j=0;jlen;j++){kong(8-m);m=t[i].jihe[j].length();coutt[i].jihe[j];}coutendl;}}voidmain(){edge*b=newedge[MAXS];inti,j,k,m,n,h,x,y,len;boolflag;stringjh[MAXS],endnode,ednode,sta;cout请输入NFA各边信息（起点条件[空为*]终点），以#结束：endl;for(i=0;iMAXS;i++){cinb[i].first;if(b[i].first==#)break;cinb[i].changeb[i].last;}N=i;/*for(j=0;jN;j++)coutb[j].firstb[j].changeb[j].lastendl;*/for(i=0;iN;i++){if(NODE.find(b[i].first)NODE.length())NODE+=b[i].first;if(NODE.find(b[i].last)NODE.length())NODE+=b[i].last;if((CHANGE.find(b[i].change)CHANGE.length())&&(b[i].change!=*))CHANGE+=b[i].change;}len=CHANGE.length();cout结点中属于终态的是：endl;cinendnode;for(i=0;iendnode.length();i++)if(NODE.find(endnode[i])NODE.length()){cout所输终态不在集合中，错误！endl;return;}//coutendnode=endnodeendl;chan*t=newchan[MAXS];t[0].ltab=b[0].first;h=1;eclouse(b[0].first[0],t[0].ltab,b);//求e-clouse//coutt[0].ltabendl;for(i=0;ih;i++){for(j=0;jt[i].ltab.length();j++)for(m=0;mlen;m++)eclouse(t[i].ltab[j],t[i].jihe[m],b);//求e-clousefor(k=0;klen;k++){//coutt[i].jihe[k]-;move(t[i],k,b);//求move(I,a)//coutt[i].jihe[k]endl;for(j=0;jt[i].jihe[k].length();j++)eclouse(t[i].jihe[k][j],t[i].jihe[k],b);//求e-clouse}for(j=0;jlen;j++){paixu(t[i].jihe[j]);//对集合排序以便比较for(k=0;kh;k++){flag=operator==(t[k].ltab,t[i].jihe[j]);if(flag)break;}if(!flag&&t[i].jihe[j].length())t[h++].ltab=t[i].jihe[j];}}coutendl状态转换矩阵如下：endl;outputfa(len,h,t);//输出状态转换矩阵//状态重新命名string*d=newstring[h];NODE.erase();coutendl重命名：endl;for(i=0;ih;i++){sta=t[i].ltab;t[i].ltab.erase();t[i].ltab='A'+i;NODE+=t[i].ltab;cout'{'sta}=t[i].ltabendl;for(j=0;jendnode.length();j++)if(sta.find(endnode[j])sta.length())d[1]=ednode+=t[i].ltab;for(k=0;kh;k++)for(m=0;mlen;m++)if(sta==t[k].jihe[m])t[k].jihe[m]=t[i].ltab;}for(i=0;iNODE.length();i++)if(ednode.find(NODE[i])ednode.length())d[0]+=NODE[i];endnode=ednode;coutendlDFA如下：endl;outputfa(len,h,t);//输出DFAcout其中终态为：endnodeendl;//DFA最小化m=2;sta.erase();flag=0;for(i=0;im;i++){//coutd[i]=d[i]endl;for(k=0;klen;k++){//coutICHANGE[k]endl;y=m;for(j=0;jd[i].length();j++){for(n=0;ny;n++){if(d[n].find(t[NODE.find(d[i][j])].jihe[k])d[n].length()||t[NODE.find(d[i][j])].jihe[k].length()==0){if(t[NODE.find(d[i][j])].jihe[k].length()==0)x=m;elsex=n;if(!sta.length()){sta+=x+48;}elseif(sta[0]!=x+48){d[m]+=d[i][j];flag=1;d[i].erase(j,1);//coutd[i]endl;j--;}break;//跳出n}}//n}//jif(flag){m++;flag=0;}//coutsta=staendl;sta.erase();}//k}//icoutendl集合划分：;for(i=0;im;i++)cout{d[i]};coutendl;//状态重新命名chan*md=newchan[m];NODE.erase();coutendl重命名：endl;for(i=0;im;i++){md[i].ltab='A'+i;NODE+=md[i].ltab;cout{d[i]}=md[i].ltabe