不確定有窮狀態(tài)自動機的確定化實驗報告.doc

精品文檔編譯原理實驗報告(二) E01214055 魯慶河1. 實驗名稱：不確定有窮狀態(tài)自動機的確定化2. 實驗目的：a) 輸入：非確定有窮狀態(tài)自動機NFA b) 輸出：確定化的有窮狀態(tài)自動機DFA3. 實驗原理：a) NFA確定化為DFA同一個字符串可以由多條通路產(chǎn)生，而在實際應用中，作為描述控制過程的自動機，通常都是確定有限自動機DFA，因此這就需要將不確定有限自動機轉(zhuǎn)換成等價的確定有限自動機，這個過程稱為不確定有限自動機的確定化，即NFA確定化為DFA。b) NFA的確定化算法 - 子集法：l 若NFA的全部初態(tài)為S1，S2，Sn，則令DFA的初態(tài)為：SS1，S2，Sn， 其中方括號用來表示若干個狀態(tài)構(gòu)成的某一狀態(tài)。l 設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中。l 重復第2步，直到K中不再有新的狀態(tài)加入為止。l 上面得到的所有狀態(tài)構(gòu)成DFA的狀態(tài)集K，轉(zhuǎn)換函數(shù)構(gòu)成DFA的F，DFA的字母表仍然是NFA的字母表。l DFA中凡是含有NFA終態(tài)的狀態(tài)都是DFA的終態(tài)。c) closure（I）函數(shù)，move(I,a)函數(shù)的假設I是NFA M狀態(tài)集K的一個子集（即IK），則定義-closure（I）為：1. 若QI，則Q-closure（I）；2. 若QI，則從Q出發(fā)經(jīng)過任意條弧而能到達的任何狀態(tài)Q，則Qclosure（I）。3. 狀態(tài)集-closure（I）稱為狀態(tài)I的閉包。假設NFA M( K,F,S,Z ),若IK，a,則定義Iaclosure（J）,其中J是所有從closure（I）出發(fā),經(jīng)過一條a弧而到達的狀態(tài)集。 NFA確定化的實質(zhì)是以原有狀態(tài)集上的子集作為DFA上的一個狀態(tài),將原狀態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有限自動機確定化。經(jīng)過確定化后，狀態(tài)數(shù)可能增加,而且可能出現(xiàn)一些等價狀態(tài)，這時就需要簡化。4. 實驗思路：(數(shù)據(jù)結(jié)構(gòu)及變量設計等) 5. 實驗小結(jié)：在寫此次試驗之初，數(shù)據(jù)結(jié)構(gòu)設計是這樣的，K,E,S,Z都用一位字符數(shù)組存儲，F(xiàn)用下面的鏈表存儲，但是最終在寫move函數(shù)時查找J集合麻煩，加之數(shù)據(jù)結(jié)構(gòu)算法的實現(xiàn)基本功不夠，在同學的指點下就從新定義了數(shù)據(jù)結(jié)構(gòu)。在新的數(shù)據(jù)結(jié)構(gòu)中，使用鄰接表來存儲轉(zhuǎn)換函數(shù)的，雖然數(shù)據(jù)結(jié)構(gòu)部分對于順序表 鏈表 鄰接表的操作很陌生，但通過此次的實驗讓我對于數(shù)據(jù)結(jié)構(gòu)中鄰接表的使用有了很好的復習和回顧，也學會了鄰接表中指針的使用和插入刪除操作此次實驗過程中，代碼雖然全部都是本人自己編寫，但很多不是我自己的思想，是從同學那剽竊來理解消化的，在別人和我講述了代碼之后，我自己獨立的去寫時，細節(jié)的地方仍然是漏洞百出，到處出錯。我的代碼能力太差，也常常因為這而自卑，但也不知如何去提升，雖然課本上的確定化會寫，算法也能夠理解和掌握，但是實現(xiàn)起來就是無從下手，所以動手能力差的同時，書本知識也得不到強化。 我會借編譯原理實驗的機會慢慢的熟悉代碼，自己去想通算法，自己去實現(xiàn)算法。我很感激姚老師的嚴厲要求，我相信我們院的老師都要像您和王愛平老師這樣的就好了！6. 附件：（程序和運行結(jié)果截圖）a) 程序：10歡迎下載10歡迎下載10歡迎下載。#include #include #include #include #define N 20 /用于控制數(shù)組的最大長度/用鄰接表存儲NFA和DFA的狀態(tài) 字母 后繼typedef struct adjvex/定義鄰接表的鄰接點域的數(shù)據(jù)表示char nextstate;/頭結(jié)點狀態(tài)的后繼狀態(tài)char arc;/弧struct adjvex *next;/指向該頭結(jié)點狀態(tài)的下一個后繼狀態(tài)的指針adjvex;typedef struct headvex/定義鄰接表的頭部的數(shù)據(jù)表示char state;/狀態(tài)adjvex *firstarc;/指向第一個后繼狀態(tài)的指針headvex;/定義兩個鄰接表的頭部，為全局數(shù)組headvex NFAN;/用鄰接表存儲的NFAheadvex DFAN;/用鄰接表存儲的DFAchar AlpN;/存儲需要輸入的行為集，即字母表void main()void designby();/函數(shù)聲明void closure(char s,char setN);/求e_closure閉包函數(shù)void Special(char DFA_startN,char new_stateNN);/確定化函數(shù)designby();int i,j;char NFA_startN;/存放NFA的初態(tài)char DFA_startN;/存放DFA的初態(tài)char NFA_finalN;/存放NFA的終態(tài)char DFA_finalN;/存放DFA的終態(tài)char new_stateNN;/存放DFA的I的二維數(shù)組 每一行為一個原NFA的一個新的狀態(tài)集，e-closure(move(I,a)for(i=0; iN; i+)NFAi.state=#;NFAi.firstarc=NULL;DFAi.state=#;DFAi.firstarc=NULL;Alpi=#;NFA_starti=#;DFA_starti=#;NFA_finali=#;DFA_finali=#;for(j=0; jN; j+)new_stateij=#;int m,n;printf(請輸入NFA: 狀態(tài)的個數(shù): bbb);scanf(%d,&n);fflush(stdin);printf( 狀態(tài)轉(zhuǎn)換個數(shù): bbb);scanf(%d,&m);fflush(stdin);printf(請輸入各狀態(tài):(狀態(tài),0/1/2)，終態(tài)輸2，非初終態(tài)輸1,初態(tài)輸0.n);/創(chuàng)建鄰接表int f;for(i=0; in; i+)/n個狀態(tài)的輸入,依次存儲到已開辟空間的鄰接表頭結(jié)點中，并根據(jù)狀態(tài)分類裝入NFA的初態(tài)終態(tài)數(shù)組中.printf(狀態(tài)%d：,i+1);scanf(%c,%d,&NFAi.state,&f);fflush(stdin);if(f=0)/輸入狀態(tài)若為初態(tài),依次存入到NFA_startN數(shù)組中for(j=0; jN & NFA_startj!=#;j+);NFA_startj=NFAi.state;if(f=2)/輸入狀態(tài)若為終態(tài),依次存入到NFA_finalN數(shù)組中for(j=0; jN & NFA_finalj!=#;j+);NFA_finalj=NFAi.state;printf(輸入完畢!nn);printf(請輸入狀態(tài)轉(zhuǎn)換函數(shù):(狀態(tài)1,狀態(tài)2,輸入字符)n);adjvex *p;/定義一個指向adjvex的指針pchar from,to,arc;int k;for(i=0; inextstate=to;p-arc=arc;for(k=0; NFAk.state!=from; k+);/結(jié)束時k的值即為匹配狀態(tài)所在的頭結(jié)點p-next=NFAk.firstarc;/前插法插入結(jié)點到頭結(jié)點后NFAk.firstarc=p;/前插法插入結(jié)點到頭結(jié)點后if(arc!=$)/輸入字符不為空，保存到AlpsN字母表中for(j=0; jN & Alpj!=#;j+)if(arc=Alpj)break;/存在則跳出，結(jié)束不保存/上循環(huán)結(jié)束的兩個可能: 1、該輸入字符已經(jīng)存在于字母表中 不存跳出，則下面的if也不會成立；/2、從0開始到#結(jié)束都沒找不到一樣的字母，結(jié)束for，記下了j.if(Alpj=#) Alpj=arc;printf(輸入完畢!nn);/求所有NFA_startN中所有初態(tài)的closure形成總的初態(tài)DFA_startN/char startNN;/for(i=0; iN; i+)/for(j=0; jN; j+)/startij=#;/for(i=0; NFA_starti!=#; i+)/依次對每個NFA初態(tài)求等價狀態(tài)放在二維數(shù)組中/closure(NFA_starti,DFA_start);/*int k;for(i=0; NFA_starti!=#; i+)/將start二維數(shù)組變到一位數(shù)組DFA_startN中for(j=0; startij!=#; j+)k=0;for(k=0;DFA_startk!=startij & DFA_startk!=#;k+);if(DFA_startk=#)DFA_startk=startij;else continue;*/k=0;while(NFAk.state!=NFA_start0)k+;closure(NFAk.state,DFA_start);/求初態(tài)的e_closure閉包/for(int z=0; zN; z+)/printf(%4c %4cn,NFA_startz,DFA_startz);Special(DFA_start,new_state);/有DFA_startN,即為new_state0通過對NFAN鄰接表依次求/for(z=0; zN; z+)/printf(%sn,new_statez);/k=0;for(i=0;iN&new_statei0!=#;i+)/尋找DFA的終態(tài)for(j=0;jN&new_stateij!=#;j+)for(f=0;fN&NFA_finalf!=#;f+)if(new_stateij=NFA_finalf)DFA_finalk=i+65;k+;break;if(new_stateij=NFA_finalf)break;/NFA和DFA的輸出：k=0;for(i=0;iN&new_statei0!=#;i+)/尋找DFA的終態(tài)for(j=0;jN&new_stateij!=#;j+)for(f=0;farc=Alpj)printf(%3c,p-nextstate);break;elsep=p-next;if(p=NULL)printf( );for(k=0;kN&DFA_finalk!=#;k+)if(DFAi.state=DFA_finalk)break;if(DFA_finalk=#)printf( 0);elseprintf( 1);printf(n);printf(每個新的狀態(tài)對應的原狀態(tài)子集如下：n);/輸出對應的NFA子集for(i=0;iN&new_statei0!=#;i+)printf(%3c,i+65);printf( );for(j=0;jN&new_stateij+1!=#;j+)printf(%c,new_stateij);printf(%c,new_stateij);printf(n);printf(新的終態(tài)如下：n);for(i=0;iarc=$)closure(p-nextstate,set);/若為空弧的話，遞歸進入該后繼狀態(tài)所對應的頭結(jié)點狀態(tài)處依次查找其空弧后繼，查找結(jié)束回到上一層后繼狀態(tài)繼續(xù)查找p=p-next;elsep=p-next;/查看該頭結(jié)點狀態(tài)的下一個后繼狀態(tài)return;void move(char FromN,char arc,char ToN)/找一個狀態(tài)集FromN的所有狀態(tài)的arc后繼狀態(tài)的集合ToNint i,j,k,t=0;adjvex *p;j=0;/首先定義j為0for(i=0; iarc=arc)for(k=0; knextstate)p=p-next;break;/該狀態(tài)若已存在ToN中，跳出循環(huán)不保存，移動指針查看下一個后繼狀態(tài)if(Tok=#)/直達結(jié)束沒有發(fā)現(xiàn)已經(jīng)存入，Tot+=p-nextstate;p=p-next;else p=p-next;void Order(char aN)/由小到大對數(shù)組中的每個字符排序int i,j;char temp;for(i=0;iN&ai!=#;i+)for(j=i+1;jN&aj!=#;j+)if(ajai)temp=ai;ai=aj;aj=temp;void Special(char DFA_startN,char new_stateNN)int i,j;char To1N,To2N;char order1N,order2N;for(i=0; iN; i+)To1i=#;To2i=#;for(i=0; iN & DFA_starti!=#;i+)new_state0i=DFA_starti;/將DFA_startN復制到new_state0,作為一個狀態(tài)int st,k,t;adjvex *p;for(st=0; stN & new_statest0!=#; st+ )DFAst.state=st+65;for(i=0; Alpi!=#; i+)for(k=0; kN; k+)To1k=#; To2k=#;/每次使用TO1，To2都要清除原有數(shù)據(jù)move(new_statest,Alpi,To1);for(j=0;To1j!=#;j+)/循環(huán)求狀態(tài)集的closure閉包(求每一個狀態(tài)的closure時，都會對上一個狀態(tài)得到的To2N從頭找不相同的存進去)closure(To1j,To2);for(j=0; jN&new_statej0!=#; j+)/將new_state和closure( move(I,a) )轉(zhuǎn)存到兩個新數(shù)組中，排序比較