編譯實驗三NFA轉換成DFA和DFA化簡要點

1、實驗三（一）NFADFA（2小時）一. 問題描述NFADFA。1. 實驗目的：學會編程實現子集構造法。2. 實驗任務：存儲NFA與DFA，編程實現子集構造法將NFA轉換成DFA。3. 實驗內容：（1）確定NFA與DFA的存儲格式，為3個以上測試NFA準備好存儲文件。（2）用C或JAVA語言編寫將NFA轉換成DFA的子集構造法的程序。（3）經測試無誤。測試不易?？汕蟪鯪FA與DFA的語言集合的某個子集（如長度小于某個N），再證實兩個語言集合完全相同?。?）測試用例參考：將下列語言用RE表示，再轉換成NFA使用：(a) 以a開頭和結尾的小字字母串；a (a|b|z)*a | a(b) 不包含三個連

2、續(xù)的b的，由字母a與b組成的字符串；(e | b | bb) (a | ab | abb)*(c) (aa|b)*(a|bb)*二算法描述1. NFA的輸入：分別輸入NFA的“字符集”、“狀態(tài)集”、“開始狀態(tài)”、“接受狀態(tài)集”、“狀態(tài)轉換表”等內容，并保存在設定的變量中。2. NFA的存儲與讀寫：將上述NFA的五元組保存在一個文本文件中。存儲格式如下所示（以下圖中NFA為例）：2 / 字符集中的字符個數 (以下兩行也可合并成一行)a b / 以空格分隔的字符集。4 / 狀態(tài)個數 (以下兩行也可合并成一行)1 2 3 4 / 狀態(tài)編號。若約定總是用從1開始的連續(xù)數字表示，則此行可省略1 / 開始

3、狀態(tài)的編號。若約定為1，則此行可省略1 / 結束狀態(tài)個數。若約定為1，則此行可省略3 / 結束狀態(tài)的編號3 2 1 / 狀態(tài)1的所有出去的轉換。按字符集中的字符順序給出，并在最左邊加上一列關于e的轉換。-1表示出錯狀態(tài)。多個狀態(tài)用逗號分隔。-1 1 -1-1 3 4-1 -1 33. 基本算法描述存儲格式如上所示，程序開始時，從文件中讀取數據以獲得NFA中的各種信息。根據子集構造法，構造相應的函數。子集構造法偽代碼如下：初始時,-closure(S0)是Dstates中唯一的狀態(tài)且未被標記;whileDstates中存在一個未標記的狀態(tài)Tdobegin標記T;for每個輸入符號adobegin

4、U:=-closure(move(T,a);ifU沒在Dstates中then將U作為一個未被標記的狀態(tài)添加到Dstates.DtranT,a:=Uendend-closure的計算將T中所有狀態(tài)壓入棧stack;將-closure(T)初始化為T;whilestack不空dobegin將棧頂元素t彈出棧;for每個這樣的狀態(tài)u：從t到u有一條標記為的邊doifu不在-closure(T)中dobegin 將u添加到-closure(T);將u壓入棧stack中endend子集構造法的流程圖：實驗三（二）DFA化簡（2小時）一. 問題描述 DFA化簡1 實驗目的：學會編程實現等價劃分法化簡DF

5、A。2 實驗任務：先完善DFA，再化簡DFA。3 實驗內容：（1）準備3個以上測試DFA文件。（2）DFA手動完善。（狀態(tài)轉換映射要是滿映射）（3）用C或JAVA語言編寫用等價劃分法化簡DFA的程序。（4）經測試無誤。測試不易。可求出兩個DFA的語言集合的某個子集（如長度小于某個N），再證實兩個語言集合完全相同?。?）編寫實驗報告。要求同實驗一，不再詳述。二算法描述1.DFA的化簡得到新的DFA之后，并沒有完成任務，因為通過NFA轉化成DFA不一定是最簡的，也就是說，有多余的狀態(tài)可以被刪除，而我們需要的是得到一個唯一的最簡的DFA12，也就是說，NFA轉化為DFA之后，還需要化簡，也就是最小化

6、。2.化簡的理論基礎DFA的化簡是指：尋找一個狀態(tài)數最少的DFAM，使得L（M）=L（M）。化簡的方法是消去DFAM中的多余狀態(tài)（或無用狀態(tài)），合并等價狀態(tài)。DFA中的多余狀態(tài)是指這樣的狀態(tài)：從開始狀態(tài)出發(fā)，讀入任何輸入串都不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。兩個狀態(tài)S和T等價是指：如果從狀態(tài)S出發(fā)能讀出某個字W而停于終態(tài)，從T出發(fā)也能讀出同樣的字W而停于終態(tài)；反之，從T出發(fā)能讀出同樣的字W而停于終態(tài)，從S出發(fā)也能讀出某個字W而停于終態(tài)。3.化簡的基本思想化簡DFA的基本思想是指導它的狀態(tài)分成一些互不相交的子集，每一個子集中的狀態(tài)都不是等價的，不同子集中的狀態(tài)可以由某個輸入串來

7、區(qū)別，最后將不能區(qū)別的每個子集用一個狀態(tài)來做代表13-15，這種方法稱為“分割法”。具體過程是：（1）將M的所有狀態(tài)分成兩個子集終態(tài)集和非終態(tài)集；（2）考察每一個子集，若發(fā)現某子集中的狀態(tài)不等價，將其劃分為兩個集合；（3）重復第（2）步，繼續(xù)考察已得到的每一個子集，直到沒有任何一個子集需要繼續(xù)劃分為止。這時DFA的狀態(tài)被分成若干個互不相交的子集。（4）從每個子集中選出一個狀態(tài)做代表即可得到最簡的DFA。三程序分析通過本設計所要求達到的目的是：充分理解和掌握NFA，DFA以及NFA確定化過程的相關概念和知識，理解和掌握子集法的相關知識和應用，現在需要編程實現對輸入NFA轉換成DFA輸出的功能。程

8、序總框圖如下：功能圖如下：4 運行結果 5. 實驗問題及心得通過此次對從NFA到DFA的轉化和DFA的化簡的設計，使我更好的理解了NFA確定化過程的相關知識，很好的理解了子集法的演算過程。還有DFA的化簡過程有了更好地理解。經過多次試驗，在正確輸入相關數據的情況下，程序能正常運行，當錯誤操作或輸入錯誤數據時，程序將應錯誤自動關閉。經過這次課程設計,也讓我深刻的認識到實踐才是最重要的。書本只能教給我們基礎知識,要怎樣運用,將那些知識真正吸收,轉化為自己的智慧,只有通過實踐才能達到。編譯原理是一門實用性很強，對我們的專業(yè)很有幫助的科目,我將會繼續(xù)努力,不斷增加自己的知識面,把編譯原理學習的更好。6

9、. 附錄#include#include#define MAXS 100using namespace std;string NODE;/結點集合string CHANGE;/終結符集合int N;/NFA邊數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+)fo

10、r(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

11、(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

12、,n,h,x,y,len;bool flag;string jhMAXS,endnode,ednode,sta;cout請輸入NFA各邊信息（起點 條件空為* 終點），以#結束：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(CHAN

13、GE.find(bi.change)CHANGE.length()&(bi.change!=*)CHANGE+=bi.change;len=CHANGE.length();cout結點中屬于終態(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(

14、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+)eclouse(ti.jihekj,ti.jihek,b);/求e-clousefor(j=0;jlen;j+)paixu(ti.jihej);/對集合排序以便比較for(k=0;kh;k+)flag=operator=(tk.ltab

15、,ti.jihej);if(flag)break;if(!flag&ti.jihej.length()th+.ltab=ti.jihej;coutendl狀態(tài)轉換矩陣如下：endl;outputfa(len,h,t);/輸出狀態(tài)轉換矩陣/狀態(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

16、.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;/DFA最小化 m=2;sta.erase();flag=0;for(i=0;im;i+)/coutdi=diendl;for(k=0;klen;k+)/

17、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=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=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.leng