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

1、實(shí)驗(yàn)三（一） NFA DFA（2 小時(shí)）一 . 問題描述NFA DFA 。1. 實(shí)驗(yàn)?zāi)康模?學(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語言編寫將NFA轉(zhuǎn)換成DFA的子集構(gòu)造法的程序。（3）經(jīng)測(cè)試無 誤。測(cè)試不易?？汕蟪?NFA與DFA的語言集合的某個(gè)子集（如長度小于某個(gè)N），再證實(shí)兩個(gè)語言集合完全相同！ （ 4）測(cè)試用例參考：將下列語言用 RE 表示，再轉(zhuǎn)換成 NFA 使用：（a）以a開頭和結(jié)尾的小字字母串；a

2、（a|b|z）*a | a（b）不包含三個(gè)連續(xù)的 b 的，由字母 a 與 b 組成的字符串； （ | 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 的存儲(chǔ)與讀寫：將上述 NFA 的五元組保存在一個(gè)文本文件中。 存儲(chǔ)格式如下所示 （以下圖中 NFA 為例）：2 / 字符集中的字符個(gè)數(shù)（以下兩行也可合并成一行）a b / 以空格分隔的字符集。4 / 狀態(tài)個(gè)數(shù) ( 以下兩行也可合并成一行 )1 2 3

3、 4 / 狀態(tài)編號(hào)。若約定總是用從 1 開始的連續(xù)數(shù)字表示，則此行可省略1 / 開始狀態(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)于 的轉(zhuǎn)換。 -1 表示出錯(cuò)狀態(tài)。多個(gè)狀態(tài)用逗號(hào)分隔。-1 1 -1-1 3 4-1 -1 3NFA 中的各種信息。根據(jù)3. 基本算法描述 存儲(chǔ)格式如上所示，程序開始時(shí)，從文件中讀取數(shù)據(jù)以獲得 子集構(gòu)造法，構(gòu)造相應(yīng)的函數(shù)。子集構(gòu)造法偽代碼如下：初始時(shí),& -closure(SO)是Dstates中唯一的狀態(tài)

4、且未被標(biāo)記 while Dstates 中存在一個(gè)未標(biāo)記的狀態(tài) T do begin 標(biāo)記 T;for 每個(gè)輸入符號(hào) a do beginU := & -closure ( move (T, a) );if U 沒在 Dstates 中 then將 U 作為一個(gè)未被標(biāo)記的狀態(tài)添加到 Dstates.Dtran T, a := Uendend& -closure 的計(jì)算將 T 中所有狀態(tài)壓入棧 stack; 將& -closure (T) 初始化為 T;while stack 不空 do begin將棧頂元素t彈出棧；for每個(gè)這樣的狀態(tài)u:從t到u有一條標(biāo)記為&

5、的邊doif u 不在& -closure ( T ) 中 do begin將 u 添加到& -closure ( T )；將u壓入棧stack中endend子集構(gòu)造法的流程圖:實(shí)驗(yàn)三（二）DFA化簡（2小時(shí)）問題描述DFA化簡1. 實(shí)驗(yàn)?zāi)康模簩W(xué)會(huì)編程實(shí)現(xiàn)等價(jià)劃分法化簡 DFA。2. 實(shí)驗(yàn)任務(wù)：先完善DFA，再化簡DFA。3實(shí)驗(yàn)內(nèi)容：（1）準(zhǔn)備3個(gè)以上測(cè)試DFA文件。（2）DFA手動(dòng)完善。（狀態(tài)轉(zhuǎn)換映射要是滿映射）（3） 用C或JAVA語言編寫用等價(jià)劃分法化簡DFA的程序。（4） 經(jīng)測(cè)試無誤。測(cè)試不易?？汕蟪鰞蓚€(gè)DFA的語言集合的某個(gè)子集（如長度 小于某個(gè)N）,再證實(shí)兩個(gè)語言集

6、合完全相同！（5）編寫實(shí)驗(yàn)報(bào)告。要求同實(shí)驗(yàn)一，不再詳述。.算法描述1. DFA的化簡得到新的DFA之后，并沒有完成任務(wù)，因?yàn)橥ㄟ^NFA轉(zhuǎn)化成DFA不一定是最簡的，也就是說，有多余的狀態(tài)可以被刪除，而我們需要的是得到一個(gè)唯一的最 簡的DFA12，也就是說，NFA轉(zhuǎn)化為DFA之后，還需要化簡，也就是最小化。2. 化簡的理論基礎(chǔ)DFA的化簡是指：尋找一個(gè)狀態(tài)數(shù)最少的DFA M，使得L（ M）=L（M '）?；喌姆椒ㄊ窍?DFA M中的多余狀態(tài)（或無用狀態(tài)），合并等價(jià)狀態(tài)。DFA中的多余狀態(tài)是指這樣的狀態(tài)：從開始狀態(tài)出發(fā)，讀入任何輸入串都不 能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)

7、。兩個(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. 化簡的基本思想化簡DFA的基本思想是指導(dǎo)它的狀態(tài)分成一些互不相交的子集，每一個(gè)子集 中的狀態(tài)都不是等價(jià)的， 不同子集中的狀態(tài)可以由某個(gè)輸入串來區(qū)別，最后將不能區(qū)別的每個(gè)子集用一個(gè)狀態(tài)來做代表13-15，這種方法稱為“分割法”。具體過程是：（1 ）將M的所有狀態(tài)分成兩個(gè)子集一一終態(tài)集和非終態(tài)集；（2） 考察每一個(gè)子集，若發(fā)現(xiàn)某子集中的狀態(tài)不等價(jià)，將其劃分為兩個(gè)集合；（3）重復(fù)第（2）步，繼續(xù)考察

8、已得到的每一個(gè)子集，直到?jīng)]有任何一個(gè)子集 需要繼續(xù)劃分為止。這時(shí) DFA的狀態(tài)被分成若干個(gè)互不相交的子集。（4 ）從每個(gè)子集中選出一個(gè)狀態(tài)做代表即可得到最簡的DFA。三.程序分析通過本設(shè)計(jì)所要求達(dá)到的目的是：充分理解和掌握NFA , DFA以及NFA確定化過程的相關(guān)概念和知識(shí)，理解和掌握子集法的相關(guān)知識(shí)和應(yīng)用，現(xiàn)在需要編程實(shí)現(xiàn)對(duì)輸入NFA轉(zhuǎn)換成DFA輸出的功能。程序總框圖如下：功能圖如下:四.運(yùn)行結(jié)果I狀態(tài)轉(zhuǎn)喚矩陣如H I la lb1331-匡命名t<23>=B-D-Er刖如"F，1 la 1>>I)EI EED博中終態(tài)為.CD竜命名.<ADE>

9、-ft <CJ -D5 =G最小化F如下i1 la lbBBARDIPi>b£s any k*ey to cont;inue五.實(shí)驗(yàn)問題及心得通過此次對(duì)從NFA到DFA的轉(zhuǎn)化和DFA的化簡的設(shè)計(jì)，使我更好的理解 了 NFA確定化過程的相關(guān)知識(shí)，很好的理解了子集法的演算過程。還有 DFA的 化簡過程有了更好地理解。經(jīng)過多次試驗(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)過這次課程設(shè)計(jì)，也讓我深刻的認(rèn)識(shí)到實(shí)踐才是最重要的。書本只能教給 我們基礎(chǔ)知識(shí)，要怎樣運(yùn)用，將那些知識(shí)真正吸收，轉(zhuǎn)化為自己的智慧，只有通過實(shí) 踐才能達(dá)到

10、。編譯原理是一門實(shí)用性很強(qiáng)，對(duì)我們的專業(yè)很有幫助的科目，我將會(huì)繼續(xù)努力，不斷增加自己的知識(shí)面，把編譯原理學(xué)習(xí)的更好。六.附錄#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;string jiheMAXS;void kong(int a

11、)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=bk.first0)if(bk.change="

12、*")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(bj.last0)>he.jihem.length()

13、he.jihem+=bj.last0; for(i=0;i<l;i+) for(j=0;j<N;j+)if(CHANGEm=bj.change0)&&(he.jihemi=bj.fi rst0)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+) cout<<'I'

14、<<CHANGEi<<" ""<<endl;cout<<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 edgeMAXS;int i,j,k,m,n,h,

15、x,y,len;bool flag;string jhMAXS,endnode,ednode,sta;coutvv"請(qǐng)輸入NFA各邊信息(起點(diǎn) 條件空為*終點(diǎn)), 以#結(jié)束： "<<endl;for(i=0;ivMAXS;i+)cin>>bi.first;if(bi.first="#") break;cin>>bi.change>>bi.last;N=i;/*for(j=0;jvN;j+)coutvvbj.firstvvbj.changevvbj.lastvvendl;*/ for(i=0;ivN;i+)i

16、f(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é)點(diǎn)中屬于終態(tài)的是： "<<endl;cin>>endnode;for(i=0;i

17、<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.ltab,b);/ 求 e-clouse/cout<<t0.ltab<<endl;f

18、or(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.jihek.length();j+) eclouse(ti.jihekj,ti.jihek,

19、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);/ 輸出狀態(tài)轉(zhuǎn)換矩陣/狀態(tài)重新命名string *d=new stringh;NOD

20、E.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+) if(sta.find(endnodej)<sta.length()

21、 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);/輸出 DFAcout<<" 其中終態(tài)為： "

22、<<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;n<y;n+)if(dn.find(tNODE.fi

23、nd(dij).jihek)<dn.length()|tN ODE.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<<" 集合劃分： "for(i=0;i<m;i+)cout<<""<<di<<""cout