《NFA到DFA的确定化及最小化》由会员分享，可在线阅读，更多相关《NFA到DFA的确定化及最小化（9页珍藏版）》请在金锄头文库上搜索。
1、NFA转化为DFA的确定化及最小化一NFA向DFA的转换从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态.DFA使用它的状态记录在NFA读入一个输入符号后可能达到的所有状态.得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最简的DFA12,也就是说，NFA转化为DFA之后，还需要化简，也就是最小化。二NFA的确定化方法子集法：1. 先把DFAW中的Q和F，置为空集；2. M的开始状
2、态qO=q0,把qO置为未标记后加入到Q中；3. 如果Q中存在未标记的状态ql,q2,qi,则对每个aE定义：6(ql,q2,qi,a)=pl,p2,pi当且仅当$(ql,q2,”，qi,a)二pl,p2,pi。如果ql,q2,qi不在Q中，则把它置为为标记后加入到Q中；如果pl,p2,pi中至少有一个是M的终态,则同时把pl,p2,pi加入到F中：然后给Q中所有的状态都标记为止；4. 重复执行(3),直到不能向Q中加入新状态，并且Q中所有的状态都有标记为止；5. 重新命名Q中的状态，最后获得等价的DFAM。二、对含变迁的NFA的确定化：1.置Q,F为空集；2.令qO=.CLOSURE(qO)
3、,并把qO置为未标记后加入到Q中；3.如果Q中存在未标记状态ql,q2,“,qi,则对每个aEE定义：d(ql,q2,”qi,a)=pl,p2,pj当且仅当d(ql,q2,”qi,a)二rl,r2,”，rke.CLOSURE(rl,r2,rk)=pl,p2,”,pj。如果pl,p2,pj不在Q中，则把它置为未标记后加入到Q中；如果pl,p2,pj中至少有一个是M的终态，则同时把pl,p2,pj加入到F中；然后给Q中的状态ql,q2,qi加上标记；4. 重复执行3,直到不能向Q中加入新状态，并且Q中所有的状态都有标记为止；5. 重新命名Q中的状态，然后获得等价的DFAM三数据结构stmctedg
4、estimgfirst;stimgchange;stimglast;；stmctchaiistrmgltab;strmgjiheMAXS;# mclude# mclude#defineMAXS100usingnamespacestd;stringNODE;/结点集合suingCHANGE;/终结符集合mtN;/NFA边数structedgestrmgfirst;strmgchange;strmglast;stmctchaiistrmgltab;strmgjiheMAXS;；voidkong(inta)int1；fbr(i=O;ia;i-H-)cout*;排序voidpaixu(strmg&a)
5、mtij；charb;for(j=Oja.length()j-H-)for(i=0:iNODE.find(ai+l)b=ai;ai=ai+l;ai+l=b;voideclouse(chai-c,suing&h匕edgeb)intk;fbr(k=0;khe.lengthQ)he+=bk.last;eclouse(bk.last0jie,b);voidmove(chan&hejntm.edgeb)intk=he.ltab.length();l=he.jiliemengthQ;for(i=O;ik;i+)for(j=Ojhe.jiliem.lengtliO)he.jihem+=bj.lastO;fb
6、r(i=O;il;i-H-)for(j=0;jhe.jiliemengthQ)he.jiliem+=b!j.lastO;输出voidoutputfa(intlen.inth,chan*t)intijjn;coutMI*;fbr(i=O;ilen;i+)coutTCHANGEiH”；coutendlHnendl;for(i=O;ih;i+)couttiltab;m=titabl亡ngth()；for(j=Ojlen;j+)kong(8-m);m=ti.jilielj.length();coutti.jihej;coutendl;voidmain()edge*b=newedgeMAXS;intij
7、,k,m,n,h,x,yjen;boolflag;strmgjhMAXS,endnode,ednode,sta;cout请输入NFA各边信息(起点条件空为*终点)，以#结束：”endl;fbr(i=O;iMAXS;i+)cinbi.fiist;if(bi.fiist=n#M)break;cinbi.changebi.last;N=i;/*for(j=0;jNj-H-)coutbj.fustbj.chaiigebj.lasteiidl;*/fbi(i=0;iNODE.lengthO)NODE+=bi.first;if(NODE.fhid(biJast)NODE.kngthO)NODE+=bi.l
8、ast;if(CHANGE.fhid(bi.change)CHANGE.length()&(bi.change!=H*H)CHANGE+=bi.change;len=CHANGE.length();cout结点中属于终态的是：”endl;ciiiendnode;fbr(i=O;iNODE.lengtli()coutf输终态不在集合中，错误!,rendl;return;/coutnendnode=neiidnodeencll;chaii*t=newchanMAXS;tO.ltab=bO.fiist;h=l;eclouse(b0.first0,t0.ltab,b);/求e-clouse/coutt
9、0.ltabendl;fbr(i=O;ih;i+)=0;jiltablength。J+)for(m=0;mlen;m+)eclouse(tiltabj,tijihem,b);求e-clousefbr(k=O;kH;move(ti,k.b);求move(I,a)/coutti.jiliekendl;for(j=Ojti.jiliekength();j卄)eclouse(ti.jihekj,ti.jihek,b);求e-clousefor(j=Ojlen;j-H-)paixu(ti.jihej);对集合排序以便比较for(k=0;kh;k+)flag=operatoi(tk.ltab,ti.jil
10、ie|j);if(flag)break;if(!flag&ti.jihej.lengthO)th-H-.ltab=ti.jihefj;coutendlH状态转换矩阵如F:nendl;outputfh(lenht)；输出状态转换矩阵/状态重新命名string*d=newstnngh;NODE.erase();coutendlH重命名:Mendl;fbr(i=O;ih;i+)sta=ti.ltab;ti.ltab.eiase();ti.ltab=rA,+i;NODE-=ti.ltab;cout,staH=Hti.ltabendl;fbr(j=0;jendnode.lengthQ;j+)if(sta
11、find(endnodej)sta.length()d1=ednode+=ti.ltab;fbr(k=O;kh;k+)foi(m=0;mlen;m-H-)if(sta=tk.jihem)tk.jihem=ti.ltab;for(i=0;iednode.lengthQ)d0+=NODEi;endnode=ednode;coutendlMDFA如下：endl;outputfa(lenji,t);/出DFAcout,r其中终态为：yendnodeendl;/DFA最小化m=2;sta.eraseQ;flag=O;/cout,dMiM=Hdiendl;fbr(k=O;klen;k+)/cout”FyCHANGEkendl;v=m；for(j=0;jdi.lengthOJ-H-)fbr(n=O;ny;n+)if(dnfind(tNODEfind(dij)jihek)dnlength()|tNODEfind(dij)jiheklength(尸=0)if(tNODE.fiiid(di|j).jiliek.lengtli()=0)x=m;elsex=n;if(!sta.lengthQ)sta-r=x+48;elseif(sta0!=x+48)flag=;di.erase(j,l);/coutdiend1;J-;break;跳出n/n/jif
