編譯實驗三(NFA轉(zhuǎn)換成DFA和DFA化簡)

1、實驗三（一）NFAàDFA（2小時）一. 問題描述NFAàDFA。1. 實驗?zāi)康模簩W(xué)會編程實現(xiàn)子集構(gòu)造法。2. 實驗任務(wù)：存儲NFA與DFA，編程實現(xiàn)子集構(gòu)造法將NFA轉(zhuǎn)換成DFA。3. 實驗內(nèi)容：（1）確定NFA與DFA的存儲格式，為3個以上測試NFA準備好存儲文件。（2）用C或JAVA語言編寫將NFA轉(zhuǎn)換成DFA的子集構(gòu)造法的程序。（3）經(jīng)測試無誤。測試不易?？汕蟪鯪FA與DFA的語言集合的某個子集（如長度小于某個N），再證實兩個語言集合完全相同！（4）測試用例參考：將下列語言用RE表示，再轉(zhuǎn)換成NFA使用：(a) 以a開頭和結(jié)尾的小字字母串；a (a|b|z)*a |

2、 a(b) 不包含三個連續(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)轉(zhuǎn)換表”等內(nèi)容，并保存在設(shè)定的變量中。2. NFA的存儲與讀寫：將上述NFA的五元組保存在一個文本文件中。存儲格式如下所示（以下圖中NFA為例）：2 / 字符集中的字符個數(shù) (以下兩行也可合并成一行)a b / 以空格分隔的字符集。4 / 狀態(tài)個數(shù) (以下兩行也可合并成一行)1 2 3 4 / 狀態(tài)編號。若約定總是用從1開始的連續(xù)數(shù)字表示，

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

4、;Dstates 中存在一個未標記的狀態(tài)T do begin 標記T;     for 每個輸入符號 a do begin U :=  -closure ( move  (T, a) ); if U 沒在Dstates中 then 將U作為一個未被標記的狀態(tài)添加到 Dstates. Dtran

5、60; T, a  := U end end-closure 的計算將T中所有狀態(tài)壓入棧stack; 將-closure (T) 初始化為T; while  stack不空 do begin 將棧頂元素t彈出棧;     for 每個這樣的狀態(tài)u：從t到u有一條標記為 的邊do       

6、; if u 不在-closure ( T )中 do begin         將u 添加到-closure ( T );將u壓入棧stack中     end end子集構(gòu)造法的流程圖：實驗三（二）DFA化簡（2小時）一. 問題描述 DFA化簡1 實驗?zāi)康模簩W(xué)會編程實現(xiàn)等價劃分法化簡DFA。2 實驗任務(wù)：先完善DFA，再化簡DFA。

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

8、0;2.化簡的理論基礎(chǔ) DFA的化簡是指：尋找一個狀態(tài)數(shù)最少的DFA  M，使得L（M）=L（M）?；喌姆椒ㄊ窍FA  M中的多余狀態(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.化簡的基本思想&

9、#160;化簡DFA的基本思想是指導(dǎo)它的狀態(tài)分成一些互不相交的子集，每一個子集中的狀態(tài)都不是等價的，不同子集中的狀態(tài)可以由某個輸入串來區(qū)別，最后將不能區(qū)別的每個子集用一個狀態(tài)來做代表13-15，這種方法稱為“分割法”。具體過程是： （1）將M的所有狀態(tài)分成兩個子集終態(tài)集和非終態(tài)集； （2）考察每一個子集，若發(fā)現(xiàn)某子集中的狀態(tài)不等價，將其劃分為兩個集合；（3）重復(fù)第（2）步，繼續(xù)考察已得到的每一個子集，直到?jīng)]有任何一個子集需要繼續(xù)劃分為止。這時DFA的狀態(tài)被分成若干個互不相交的子集。 （4）從每個子集中選出一個狀態(tài)做代表即可得到最簡的DFA。三程序分析通過本設(shè)計所要

10、求達到的目的是：充分理解和掌握NFA，DFA以及NFA確定化過程的相關(guān)概念和知識，理解和掌握子集法的相關(guān)知識和應(yīng)用，現(xiàn)在需要編程實現(xiàn)對輸入NFA轉(zhuǎn)換成DFA輸出的功能。程序總框圖如下：功能圖如下：4 運行結(jié)果 5. 實驗問題及心得通過此次對從NFA到DFA的轉(zhuǎn)化和DFA的化簡的設(shè)計，使我更好的理解了NFA確定化過程的相關(guān)知識，很好的理解了子集法的演算過程。還有DFA的化簡過程有了更好地理解。經(jīng)過多次試驗，在正確輸入相關(guān)數(shù)據(jù)的情況下，程序能正常運行，當錯誤操作或輸入錯誤數(shù)據(jù)時，程序?qū)?yīng)錯誤自動關(guān)閉。 經(jīng)過這次課程設(shè)計,也讓我深刻的認識到實踐才是最重要的。書本只能教給我們基礎(chǔ)知識,要怎樣

11、運用,將那些知識真正吸收,轉(zhuǎn)化為自己的智慧,只有通過實踐才能達到。編譯原理是一門實用性很強，對我們的專業(yè)很有幫助的科目,我將會繼續(xù)努力,不斷增加自己的知識面,把編譯原理學(xué)習(xí)的更好。6. 附錄#include<iostream>#include<string>#define MAXS 100using namespace std;string NODE;/結(jié)點集合string CHANGE;/終結(jié)符集合int N;/NFA邊數(shù)struct edgestring first;string change;string last;struct chanstring ltab;s

12、tring jiheMAXS;void kong(int a)int i;for(i=0;i<a;i+)cout<<' '/排序void paixu(string &a)int i,j;char b;for(j=0;j<a.length();j+)for(i=0;i<a.length();i+)if(NODE.find(ai)>NODE.find(ai+1)b=ai;ai=ai+1;ai+1=b;void eclouse(char c,string &he,edge b)int k;for(k=0;k<N;k+)if(c

13、=bk.first0)if(bk.change="*")if(he.find(bk.last)>he.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;i<k;i+)for(j=0;j<N;j+)if(CHANGEm=bj.change0)&&(he.ltabi=bj.first0)if(he.jihem.find(b

14、j.last0)>he.jihem.length()he.jihem+=bj.last0;for(i=0;i<l;i+)for(j=0;j<N;j+)if(CHANGEm=bj.change0)&&(he.jihemi=bj.first0)if(he.jihem.find(bj.last0)>he.jihem.length()he.jihem+=bj.last0;/輸出void outputfa(int len,int h,chan *t)int i,j,m;cout<<" I "for(i=0;i<len;i+)c

15、out<<'I'<<CHANGEi<<" "cout<<endl<<"-"<<endl;for(i=0;i<h;i+)cout<<' '<<ti.ltab;m=ti.ltab.length();for(j=0;j<len;j+)kong(8-m);m=ti.jihej.length();cout<<ti.jihej;cout<<endl;void main()edge *b=new edgeM

16、AXS;int i,j,k,m,n,h,x,y,len;bool flag;string jhMAXS,endnode,ednode,sta;cout<<"請輸入NFA各邊信息（起點 條件空為* 終點），以#結(jié)束："<<endl;for(i=0;i<MAXS;i+)cin>>bi.first;if(bi.first="#")break;cin>>bi.change>>bi.last;N=i;/*for(j=0;j<N;j+)cout<<bj.first<<bj

17、.change<<bj.last<<endl;*/for(i=0;i<N;i+) if(NODE.find(bi.first)>NODE.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é)

18、點中屬于終態(tài)的是："<<endl;cin>>endnode;for(i=0;i<endnode.length();i+)if(NODE.find(endnodei)>NODE.length()cout<<"所輸終態(tài)不在集合中，錯誤！"<<endl;return;/cout<<"endnode="<<endnode<<endl;chan *t=new chanMAXS;t0.ltab=b0.first;h=1;eclouse(b0.first0,t0.

19、ltab,b);/求e-clouse/cout<<t0.ltab<<endl;for(i=0;i<h;i+)for(j=0;j<ti.ltab.length();j+)for(m=0;m<len;m+)eclouse(ti.ltabj,ti.jihem,b);/求e-clousefor(k=0;k<len;k+)/cout<<ti.jihek<<"->"move(ti,k,b);/求move(I,a)/cout<<ti.jihek<<endl;for(j=0;j<ti

20、.jihek.length();j+)eclouse(ti.jihekj,ti.jihek,b);/求e-clousefor(j=0;j<len;j+)paixu(ti.jihej);/對集合排序以便比較for(k=0;k<h;k+)flag=operator=(tk.ltab,ti.jihej);if(flag)break;if(!flag&&ti.jihej.length()th+.ltab=ti.jihej;cout<<endl<<"狀態(tài)轉(zhuǎn)換矩陣如下："<<endl;outputfa(len,h,t);/

21、輸出狀態(tài)轉(zhuǎn)換矩陣/狀態(tài)重新命名string *d=new stringh;NODE.erase();cout<<endl<<"重命名："<<endl;for(i=0;i<h;i+)sta=ti.ltab;ti.ltab.erase();ti.ltab='A'+i;NODE+=ti.ltab;cout<<''<<sta<<"="<<ti.ltab<<endl;for(j=0;j<endnode.length();j+)

22、if(sta.find(endnodej)<sta.length()d1=ednode+=ti.ltab;for(k=0;k<h;k+)for(m=0;m<len;m+)if(sta=tk.jihem)tk.jihem=ti.ltab;for(i=0;i<NODE.length();i+)if(ednode.find(NODEi)>ednode.length()d0+=NODEi;endnode=ednode;cout<<endl<<"DFA如下："<<endl;outputfa(len,h,t);/輸出DF

23、Acout<<"其中終態(tài)為："<<endnode<<endl;/DFA最小化 m=2;sta.erase();flag=0;for(i=0;i<m;i+)/cout<<"d"<<i<<"="<<di<<endl;for(k=0;k<len;k+)/cout<<"I"<<CHANGEk<<endl;y=m;for(j=0;j<di.length();j+)for(n=0

24、;n<y;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);/cout<<di<<endl;j-;break;/跳出n/n/jif(flag)m+;flag=0;/cout<<"sta="<<sta<<endl; sta.erase();/k/icout<<endl<<"集合劃分："