編譯實(shí)驗(yàn)三(NFA轉(zhuǎn)換成DFA和DFA化簡(jiǎn))

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

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

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

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

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

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

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

8、0;2.化簡(jiǎn)的理論基礎(chǔ) DFA的化簡(jiǎn)是指：尋找一個(gè)狀態(tài)數(shù)最少的DFA  M，使得L（M）=L（M）?；?jiǎn)的方法是消去DFA  M中的多余狀態(tài)（或無(wú)用狀態(tài)），合并等價(jià)狀態(tài)。 DFA中的多余狀態(tài)是指這樣的狀態(tài)：從開(kāi)始狀態(tài)出發(fā)，讀入任何輸入串都不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒(méi)有通路到達(dá)終態(tài)。 兩個(gè)狀態(tài)S 和T等價(jià)是指：如果從狀態(tài)S出發(fā)能讀出某個(gè)字W而停于終態(tài)，從T出發(fā)也能讀出同樣的字W而停于終態(tài)；反之，從T出發(fā)能讀出同樣的字W而停于終態(tài)，從S出發(fā)也能讀出某個(gè)字W而停于終態(tài)。  3.化簡(jiǎn)的基本思想&

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

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

11、運(yùn)用,將那些知識(shí)真正吸收,轉(zhuǎn)化為自己的智慧,只有通過(guò)實(shí)踐才能達(dá)到。編譯原理是一門(mén)實(shí)用性很強(qiáng)，對(duì)我們的專(zhuān)業(yè)很有幫助的科目,我將會(huì)繼續(xù)努力,不斷增加自己的知識(shí)面,把編譯原理學(xué)習(xí)的更好。6. 附錄#include<iostream>#include<string>#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;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<<"請(qǐng)輸入NFA各邊信息（起點(diǎn) 條件空為* 終點(diǎn)），以#結(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、點(diǎn)中屬于終態(tài)的是："<<endl;cin>>endnode;for(i=0;i<endnode.length();i+)if(NODE.find(endnodei)>NODE.length()cout<<"所輸終態(tài)不在集合中，錯(cuò)誤！"<<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);/對(duì)集合排序以便比較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<<"集合劃分："