不確定有窮自動(dòng)機(jī)的確定化編譯原理實(shí)驗(yàn)報(bào)告

1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱不確定有窮自動(dòng)機(jī)的確定化實(shí)驗(yàn)時(shí)間2014年4月10日院系管理信息工程學(xué)院班級(jí)11計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)201101020109姓名姜高1 實(shí)驗(yàn)?zāi)康牟淮_定有窮自動(dòng)機(jī)的確定化2 實(shí)驗(yàn)原理用子集構(gòu)造算法構(gòu)造子集加入子集族中直到收斂（所有構(gòu)造的子集都已存在于子集族）為止。如原來不確定有窮自動(dòng)機(jī)的五元組形式為：M=（K，&，F(xiàn)，S，Z），其中K為狀態(tài)集，&為字母表，F(xiàn)為轉(zhuǎn)換函數(shù)，S為初始態(tài)，Z為終態(tài)集。用子集族S代替K,新的轉(zhuǎn)換函數(shù)D代替F,形成新的五元組M=（S,&,D,S,Z）即將原不確定有窮自動(dòng)機(jī)轉(zhuǎn)換為確定有窮自動(dòng)機(jī)。3 實(shí)驗(yàn)內(nèi)容（ 1） 閉包計(jì)算：closure（I）（ 2

2、） 轉(zhuǎn)換函數(shù)：move（I,a）4 、偽代碼假定構(gòu)造的子集族為S=(T1，T2。)，K為狀態(tài)集：1) )開始，令closure(K0內(nèi)S中唯一成員，并且未被標(biāo)記2) WHILE(C中存在尚未被標(biāo)記的子集T)DO標(biāo)記T;For每輸入字母aDOU:=closure(move(T,a);IfU不在S中then將U作為未被標(biāo)記的子集加在S中5 .代碼實(shí)現(xiàn)#include#include#defineMAXS100usingnamespacestd;stringNODE;/結(jié)點(diǎn)集合stringCHANGE;/終結(jié)符集合/intN;/NFA邊數(shù)structedgestringfirst;stringcha

3、nge;stringlast;structchanstringltab;stringjiheMAXS;voidkong(inta)inti;for(i=0;ia;i+)cout;/排序voidpaixu(string&a)inti,j;charb;for(j=0;ja.length();j+)for(i=0;iNODE.find(ai+1)b=ai;ai=ai+1;ai+1=b;voideclouse(charc,string&he,edgeb)intk;for(k=0;khe.length()he+=bk.last;eclouse(bk.last0,he,b);voidmove(chan&h

4、e,intm,edgeb)inti,j,k,l;k=he.ltab.length();l=he.jihem.length();for(i=0;ik;i+)for(j=0;jhe.jihem.length()he.jihem+=bj.last0;for(i=0;il;i+)for(j=0;jhe.jihem.length()he.jihem+=bj.last0;/輸出voidoutputfa(intlen,inth,chan*t)inti,j,m;coutI;for(i=0;ilen;i+)coutICHANGEi;endl;coutendlfor(i=0;ih;i+)coutti.ltab;m

5、=ti.ltab.length();for(j=0;jlen;j+)kong(8-m);m=ti.jihej.length();coutti.jihej;coutendl;voidmain()edge*b=newedgeMAXS;inti,j,k,m,n,h,x,y,len;boolflag;stringjhMAXS,endnode,ednode,sta;cout”請(qǐng)輸入NFA各邊信息(起點(diǎn)條件空為*終點(diǎn))，以#結(jié)束:endl;for(i=0;ibi.first;if(bi.first=#)break;cinbi.changebi.last;N=i;/*for(j=0;jN;j+)coutbj

6、.firstbj.changebj.lastendl;*/for(i=0;iNODE.length()NODE+=bi.first;if(NODE.find(bi.last)NODE.length()NODE+=bi.last;if(CHANGE.find(bi.change)CHANGE.length()&(bi.change!=*)CHANGE+=bi.change;len=CHANGE.length();cout”結(jié)點(diǎn)中屬于終態(tài)的是：endnode;for(i=0;iNODE.length()cout所輸終態(tài)不在集合中，錯(cuò)誤！endl;return;/coutendnode=endnod

7、eendl;chan*t=newchanMAXS;t0.ltab=b0.first;h=1;eclouse(b0.first0,t0.ltab,b);/求e-clouse/coutt0.ltabendl;for(i=0;ih;i+)for(j=0;jti.ltab.length();j+)for(m=0;mlen;m+)eclouse(ti.ltabj,ti.jihem,b);/求e-clousefor(k=0;klen;k+)/coutti.jihek;move(ti,k,b);/求move(I,a)/coutti.jihekendl;for(j=0;jti.jihek.length();j

8、+)eclouse(ti.jihekj,ti.jihek,b);/求e-clousefor(j=0;jlen;j+)paixu(ti.jihej);/對(duì)集合排序以便比較for(k=0;kh;k+)flag=operator=(tk.ltab,ti.jihej);if(flag)break;if(!flag&ti.jihej.length()th+.ltab=ti.jihej;coutendl狀態(tài)轉(zhuǎn)換矩陣如下：endl;outputfa(len,h,t);/輸出狀態(tài)轉(zhuǎn)換矩陣/狀態(tài)重新命名string*d=newstringh;NODE.erase();coutendl命名：endl;for(i=

9、0;ih;i+)sta=ti.ltab;ti.ltab.erase();ti.ltab=A+i;NODE+=ti.ltab;coutsta=ti.ltabendl;for(j=0;jendnode.length();j+)if(sta.find(endnodej)sta.length()d1=ednode+=ti.ltab;for(k=0;kh;k+)for(m=0;mlen;m+)if(sta=tk.jihem)tk.jihem=ti.ltab;for(i=0;iednode.length()d0+=NODEi;endnode=ednode;coutendlDFA如下：endl;output

10、fa(len,h,t);/輸出DFAcout”其中終態(tài)為：endnodeendl;/DFA最小化m=2;sta.erase();flag=0;for(i=0;im;i+)/coutdi=diendl;for(k=0;klen;k+)/coutICHANGEkendl;y=m;for(j=0;jdi.length();j+)for(n=0;ny;n+)if(dn.find(tNODE.find(dij).jihek)dn.length()|tNODE.find(dij).jihek.length()=0)if(tNODE.find(dij).jihek.length()=0)x=m;elsex=

11、n;if(!sta.length()sta+=x+48;elseif(sta0!=x+48)dm+=dij;flag=1;di.erase(j,1);/coutdiendl;j-;break;跳出n/n/jif(flag)m+;flag=0;/coutsta=staendl;sta.erase();/k/icoutendl”集合戈份：for(i=0;im;i+)coutdi;coutendl;狀態(tài)重新命名chan*md=newchanm;NODE.erase();coutendl命名：endl;for(i=0;im;i+)mdi.ltab=A+i;NODE+=mdi.ltab;coutdi=mdi.ltabendl;for(i=0;im;i+)for(k=0;klen;k+)for(j=0;jh;j+)if(di0=tj.ltab0)for(n=0;nm;n+)if(!tj.jihek.length()break;elseif(dn.find(tj.jihek)dn.length()mdi.jihek=mdn.ltab;break;break;ednode.erase();for(i=0;im;