有限狀態(tài)自動機(jī)的確定化.doc

有限狀態(tài)自動機(jī)的確定化姓名：翟彥清 學(xué)號：E10914127一、實(shí)驗(yàn)?zāi)康脑O(shè)計并實(shí)現(xiàn)將NFA確定化為DFA的子集構(gòu)造算法，從而更好地理解有限自動機(jī)之間的等價性，掌握詞法分析器自動產(chǎn)生器的構(gòu)造技術(shù)。該算法也是構(gòu)造LR分析器的基礎(chǔ)。輸入： 非確定有限（窮）狀態(tài)自動機(jī)。輸出： 確定化的有限（窮）狀態(tài)自動機(jī)二、實(shí)驗(yàn)原理一個確定的有限自動機(jī)（DFA）M可以定義為一個五元組，M（K，F(xiàn)，S，Z），其中：（1） K是一個有窮非空集，集合中的每個元素稱為一個狀態(tài)；（2） 是一個有窮字母表，中的每個元素稱為一個輸入符號；（3） F是一個從KK的單值轉(zhuǎn)換函數(shù)，即F（R，a）Q，（R，QK）表示當(dāng)前狀態(tài)為R，如果輸入字符a，則轉(zhuǎn)到狀態(tài)Q，狀態(tài)Q稱為狀態(tài)R的后繼狀態(tài)；（4） SK，是惟一的初態(tài)；（5） ZK，是一個終態(tài)集。由定義可見，確定有限自動機(jī)只有惟一的一個初態(tài)，但可以有多個終態(tài)，每個狀態(tài)對字母表中的任一輸入符號，最多只有一個后繼狀態(tài)。 對于DFA M，若存在一條從某個初態(tài)結(jié)點(diǎn)到某一個終態(tài)結(jié)點(diǎn)的通路，則稱這條通路上的所有弧的標(biāo)記符連接形成的字符串可為DFA M所接受。若M的初態(tài)結(jié)點(diǎn)同時又是終態(tài)結(jié)點(diǎn)，則稱可為M所接受（或識別），DFA M所能接受的全部字符串（字）組成的集合記作L（M）。一個不確定有限自動機(jī)（NFA）M可以定義為一個五元組，M（K，F(xiàn)，S，Z），其中：（1） k是一個有窮非空集，集合中的每個元素稱為一個狀態(tài)；（2） 是一個有窮字母表，中的每個元素稱為一個輸入符號；（3） F是一個從KK的子集的轉(zhuǎn)換函數(shù)；（4） SK，是一個非空的初態(tài)集；（5） ZK，是一個終態(tài)集。由定義可見，不確定有限自動機(jī)NFA與確定有限自動機(jī)DFA的主要區(qū)別是：（1）NFA的初始狀態(tài)S為一個狀態(tài)集，即允許有多個初始狀態(tài)；（2）NFA中允許狀態(tài)在某輸出邊上有相同的符號，即對同一個輸入符號可以有多個后繼狀態(tài)。即DFA中的F是單值函數(shù)，而NFA中的F是多值函數(shù)。因此，可以將確定有限自動機(jī)DFA看作是不確定有限自動機(jī)NFA的特例。和DFA一樣，NFA也可以用矩陣和狀態(tài)轉(zhuǎn)換圖來表示。對于NFA M，若存在一條從某個初態(tài)結(jié)點(diǎn)到某一個終態(tài)結(jié)點(diǎn)的通路，則稱這條通路上的所有弧的標(biāo)記（除外）連接形成的字符串可為M所接受。NFA M所能接受的全部字符串（字）組成的集合記作L（M）。由于DFA是NFA的特例，所以能被DFA所接受的符號串必能被NFA所接受。設(shè)M1和M2是同一個字母集上的有限自動機(jī)，若L（M1）L（M2），則稱有限自動機(jī)M1和M2等價。由以上定義可知，若兩個自動機(jī)能夠接受相同的語言，則稱這兩個自動機(jī)等價。DFA是NFA的特例，因此對于每一個NFA M1總存在一個DFA M2，使得L（M1）L（M2）。即一個不確定有限自動機(jī)能接受的語言總可以找到一個等價的確定有限自動機(jī)來接受該語言。NFA確定化為DFA同一個字符串可以由多條通路產(chǎn)生，而在實(shí)際應(yīng)用中，作為描述控制過程的自動機(jī)，通常都是確定有限自動機(jī)DFA，因此這就需要將不確定有限自動機(jī)轉(zhuǎn)換成等價的確定有限自動機(jī)，這個過程稱為不確定有限自動機(jī)的確定化，即NFA確定化為DFA。下面介紹一種NFA的確定化算法，這種算法稱為子集法：（1） 若NFA的全部初態(tài)為S1，S2，Sn，則令DFA的初態(tài)為：SS1，S2，Sn，其中方括號用來表示若干個狀態(tài)構(gòu)成的某一狀態(tài)。（2） 設(shè)DFA的狀態(tài)集K中有一狀態(tài)為Si，Si+1，Sj，若對某符號a，在NFA中有F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 則令F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 為DFA的一個轉(zhuǎn)換函數(shù)。若 Si，Si+1，Sk 不在K中，則將其作為新的狀態(tài)加入到K中。（3） 重復(fù)第2步，直到K中不再有新的狀態(tài)加入為止。（4） 上面得到的所有狀態(tài)構(gòu)成DFA的狀態(tài)集K，轉(zhuǎn)換函數(shù)構(gòu)成DFA的F，DFA的字母表仍然是NFA的字母表。（5） DFA中凡是含有NFA終態(tài)的狀態(tài)都是DFA的終態(tài)。對于上述NFA確定化算法子集法，還可以采用另一種操作性更強(qiáng)的描述方式，下面我們給出其詳細(xì)描述。首先給出兩個相關(guān)定義。 假設(shè)I是NFA M狀態(tài)集K的一個子集（即IK），則定義-closure（I）為：（1） 若QI，則Q-closure（I）；（2） 若QI，則從Q出發(fā)經(jīng)過任意條弧而能到達(dá)的任何狀態(tài)Q，則Q-closure（I）。狀態(tài)集-closure（I）稱為狀態(tài)I的閉包。假設(shè)NFA M（K，F(xiàn)，S，Z），若IK，a，則定義Ia-closure（J），其中J是所有從-closure（I）出發(fā)，經(jīng)過一條a弧而到達(dá)的狀態(tài)集。NFA確定化的實(shí)質(zhì)是以原有狀態(tài)集上的子集作為DFA上的一個狀態(tài)，將原狀態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有限自動機(jī)確定化。經(jīng)過確定化后，狀態(tài)數(shù)可能增加，而且可能出現(xiàn)一些等價狀態(tài)，這時就需要簡化。三、源程序#include#include#define MAXS 100using namespace std;string NODE; /結(jié)點(diǎn)集合string CHANGE; /終結(jié)符集合int N; /NFA邊數(shù)struct edgestring first;string change;string last;struct chanstring ltab;string jiheMAXS;void kong(int a)int i;for(i=0;ia;i+) cout ;/排序void paixu(string &a)int i,j;char b;for(j=0;ja.length();j+) for(i=0;iNODE.find(ai+1) b=ai; ai=ai+1; ai+1=b; void eclouse(char c,string &he,edge b)int k;for(k=0;khe.length() he+=bk.last; eclouse(bk.last0,he,b); void move(chan &he,int m,edge b)int i,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;/輸出void outputfa(int len,int h,chan *t)int i,j,m;cout I ;for(i=0;ilen;i+) coutICHANGEi ;coutendl-endl;for(i=0;ih;i+) cout ti.ltab; m=ti.ltab.length(); for(j=0;jlen;j+) kong(8-m); m=ti.jihej.length(); coutti.jihej; coutendl;void main()edge *b=new edgeMAXS;int i,j,k,m,n,h,x,y,len;bool flag;string jhMAXS,endnode,ednode,sta;cout請輸入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.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)不在集合中，錯誤！endl; return; /coutendnode=endnodeendl;chan *t=new chanMAXS; 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-clouse for(k=0;klen;k+) /coutti.jihek; move(ti,k,b); /求move(I,a) /coutti.jihekendl; for(j=0;jti.jihek.length();j+) eclouse(ti.jihekj,ti.jihek,b); /求e-clouse for(j=0;jlen;j+) paixu(ti.jihej); /對集合排序以便比較 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=new stringh;NODE.erase();coutendl重命名：endl;for(i=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;outputfa(len,h,t); /輸出DFAcout其中終態(tài)為：endnodeendl;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; else x=n; if(!sta.length() sta+=x+48; else if(sta0!=x+48) dm+=dij; flag=1; di.erase(j,1); /coutdiendl; j-; break; /跳出n /n /j if(flag) m+;flag=0; /coutsta=staendl; sta.erase(); /k/icoutendl集合劃分：;for(i=0;im;i+) coutdi ;coutendl;/狀態(tài)重新命名chan *md=new chanm; 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; else if(dn.find(