非確定有限自動(dòng)機(jī)的確定化

1、課程設(shè)計(jì)報(bào)告課程：編譯原理學(xué)號(hào)：姓名： 班級：教師：時(shí)間：2014.5-2014.6.20計(jì)算機(jī)科學(xué)與技術(shù)系設(shè)計(jì)名稱：非確定有限自動(dòng)機(jī)的確定化設(shè)計(jì)內(nèi)容、目的與要求：設(shè)計(jì)內(nèi)容：編程實(shí)現(xiàn)對輸入NFA轉(zhuǎn)換成DFA輸出的功能。設(shè)計(jì)要求：輸入非確定的有限自動(dòng)機(jī)，輸出確定化的有限自動(dòng)機(jī)。設(shè)計(jì)目的：實(shí)現(xiàn)NFA到DFA的轉(zhuǎn)化。計(jì)劃與進(jìn)度安排：2014.5.262014.5.30 預(yù)設(shè)計(jì)的基礎(chǔ)上，進(jìn)一步查閱資料，完善設(shè)計(jì)方案，形成 書面材料。2014.5.312014.6.10 設(shè)計(jì)總體方案，構(gòu)建繪制流程框圖，編寫代碼，上機(jī)調(diào)試。2014.6.112014.6.17 測試程序，優(yōu)化代碼，增強(qiáng)功能，撰寫設(shè)計(jì)報(bào)告。

2、2014.6.182014.6.20 繼續(xù)測試代碼、檢查設(shè)計(jì)報(bào)告，準(zhǔn)備參加答辯，然后根據(jù) 教師反饋意見，修改、完善設(shè)計(jì)報(bào)告。設(shè)計(jì)過程、步驟（可加頁）：1.需求分析 由于很多計(jì)算機(jī)系統(tǒng)都配有多個(gè)高級語言的編譯程序，對有些高級語言甚至配置了幾個(gè)不同性能的編譯程序。從功能上看，一個(gè)編譯程序就是一個(gè)語言翻譯程序。語言翻譯程序把源語言書寫的程序翻譯成目標(biāo)語言的等價(jià)程序。經(jīng)過編譯程序的設(shè)計(jì)可以大大提高學(xué)生的編程能力。 編譯程序的工作過程通常是詞法分析、語法分析、語義分析、代碼生成、代碼優(yōu)化。由于現(xiàn)在有很多詞法分析程序工具都是基于有窮自動(dòng)機(jī)的，而詞法分析又是語法分析的基礎(chǔ)，所以我們有必要進(jìn)行有窮自動(dòng)機(jī)的確定

3、化和最小化。編譯程序的這些過程的執(zhí)行先后就構(gòu)成了編譯程序的邏輯結(jié)構(gòu)。有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。正規(guī)表達(dá)式與自動(dòng)機(jī)理論在詞法構(gòu)造乃至整個(gè)編譯器構(gòu)造過程中起著至關(guān)重要的作用，同時(shí)它們被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域，它們與計(jì)算機(jī)其它學(xué)科之間也有著很大的聯(lián)系。2.設(shè)計(jì)需知2.1 NFA和DFA的概念NFA(nondeterministic finite-state automata)即非確定有限自動(dòng)機(jī), 一個(gè)非確定的有限自動(dòng)機(jī)NFA M是

4、一個(gè)五元式: NFA M=(S, , , S0, F)其中 S有限狀態(tài)集 輸入符號(hào)加上,即自動(dòng)機(jī)的每個(gè)結(jié)點(diǎn)所射出的弧可以是中一個(gè)字符或是. S0初態(tài)集 F終態(tài)集 轉(zhuǎn)換函數(shù) S 2S (2S -S的冪集S的子集構(gòu)成的集合）DFA(deterministic finite-state automata)即確定有限自動(dòng)機(jī)，一個(gè)確定的有限自動(dòng)機(jī)DFA M是一個(gè)五元式: M=(S, ，, S0, Z) 其中: S 有限狀態(tài)集 輸入字母表 映射函數(shù)(也稱狀態(tài)轉(zhuǎn)換函數(shù)) SS (s,a)=S , S, S S, a S0 初始狀態(tài) S0 S Z終止?fàn)顟B(tài)集 ZS2.2 NFA和DFA之間的聯(lián)系在非確定的有限自

5、動(dòng)機(jī)NFA中,由于某些狀態(tài)的轉(zhuǎn)移需從若干個(gè)可能的后續(xù)狀態(tài)中進(jìn)行選擇，故一個(gè)NFA對符號(hào)串的識(shí)別就必然是一個(gè)試探的過程。這種不確定性給識(shí)別過程帶來的反復(fù)，無疑會(huì)影響到FA的工作效率。而DFA則是確定的,將NFA轉(zhuǎn)化為DFA將大大提高工作效率,因此將NFA轉(zhuǎn)化為DFA是有其一定必要的。3.設(shè)計(jì)方案 (1) 如果讀入NFA，則將其轉(zhuǎn)化為DFA并最小化，輸入測試字符串，輸出測試結(jié)果。 (2）如果讀入DFA,則直接將其最小化，輸入測試字符串，輸出測試結(jié)果。4. DFA實(shí)現(xiàn)原理4.1 NFA轉(zhuǎn)換成等價(jià)的DFA將NFA轉(zhuǎn)換成等價(jià)的DFA里，NFA到相應(yīng)的DFA的構(gòu)造的基本思想是讓DFA的每一個(gè)狀態(tài)對應(yīng)NFA

6、的一組狀態(tài)。也就是說讓DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài)，在讀入輸入符號(hào)之后，DFA處在a1a2.an那樣一個(gè)狀態(tài)，該狀態(tài)表示這個(gè)NFA的狀態(tài)的一個(gè)子集T，T是從NFA的開始狀態(tài)沿著某個(gè)標(biāo)記為a1a2.an可以達(dá)到的那些狀態(tài)構(gòu)成的。對狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：(1) 狀態(tài)集合I的-閉包，表示為-closure(I)，定義為一狀態(tài)集，是狀態(tài)集中的任何狀態(tài)S經(jīng)任意條弧而能夠到達(dá)的狀態(tài)的集合。(2) 狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。4.2 NFA的確定化 1.子集法先把

7、DFA M中的Q和F置為空集；M的開始狀態(tài)q0=q0，把q0置為未標(biāo)記后加入到Q中；如果Q中存在未標(biāo)記的狀態(tài)q1,q2,，qi，則對每個(gè)a定義：(q1,q2,，qi,a)=p1,p2,pi當(dāng)且僅當(dāng)(q1,q2,，qi,a)=p1,p2,pi。如果q1,q2,，qi不在Q中，則把它置為為標(biāo)記后加入到Q中；如果p1,p2,pi中至少有一個(gè)是M的終態(tài)，則同時(shí)把p1,p2,pi加入到F中；然后給Q中所有的狀態(tài)都標(biāo)記為止；重復(fù)執(zhí)行（3），直到不能向Q中加入新狀態(tài)，并且Q中所有的狀態(tài)都有標(biāo)記為止；重新命名Q中的狀態(tài)，最后獲得等價(jià)的DFA M。 2.對含變遷的NFA的確定化：置Q, F為空集；令q0=_CL

8、OSURE(q0),并把q0置為未標(biāo)記后加入到Q中；如果Q中存在未標(biāo)記狀態(tài)q1,q2,qi,則對每個(gè)a定義：d(q1,q2,qi,a)=p1,p2,pj當(dāng)且僅當(dāng)d(q1,q2,qi,a)=r1,r2,rk, _CLOSURE(r1,r2,rk)= p1,p2,pj。如果p1,p2,pj不在Q中，則把它置為未標(biāo)記后加入到Q中；如果p1,p2,pj中至少有一個(gè)是M的終態(tài)，則同時(shí)把p1,p2,pj加入到F中；然后給Q中的狀態(tài)q1,q2,qi加上標(biāo)記；重復(fù)執(zhí)行，直到不能向Q中加入新狀態(tài)，并且Q中所有的狀態(tài)都有標(biāo)記為止；重新命名Q中的狀態(tài)，然后獲得等價(jià)的DFA M4.3實(shí)現(xiàn)方法(1)有窮自動(dòng)機(jī)的確定化：

9、在main()函數(shù)中通過使用move()和eclouse()和outputfa()函數(shù)來實(shí)現(xiàn)；(2)確定的有窮自動(dòng)機(jī)的最小化：在main()函數(shù)中使用chan結(jié)構(gòu)體來實(shí)現(xiàn)，在該函數(shù)中還調(diào)用了outputfa()函數(shù)。4.4設(shè)計(jì)流程圖 1.輸入NFA各邊信息，通過輸入（起點(diǎn) 條件空為* 終點(diǎn)）三項(xiàng)進(jìn)行輸入以#為輸入結(jié)束；然后再輸入各結(jié)點(diǎn)中的終結(jié)點(diǎn)；輸入完成后系統(tǒng)開始執(zhí)行，先生成NFA狀態(tài)轉(zhuǎn)換矩陣，重命名，輸出DFA狀態(tài)轉(zhuǎn)換矩陣，最后對DFA狀態(tài)轉(zhuǎn)換矩陣進(jìn)行最小化輸出。NFA-DFA處理流程圖如下圖圖4.4-1所示。圖4.4-1 NFA-DFA處理流程圖2.NFA轉(zhuǎn)換為DFA的原理及過程通過以下例

10、子說明： 假如輸入的NFA如圖4.4-2所示： 圖4.4-2 NFA狀態(tài)轉(zhuǎn)換圖對于圖4.2-2中的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換矩陣為：在圖4.2-2中的狀態(tài)轉(zhuǎn)換圖加一個(gè)起始狀態(tài)X和結(jié)束狀態(tài)Y，I為起始節(jié)點(diǎn)X經(jīng)過一個(gè)或多個(gè)邊到達(dá)的狀態(tài)集，Ia為X,1經(jīng)過a邊到達(dá)的結(jié)點(diǎn)的閉包，Ib經(jīng)過b邊到達(dá)的結(jié)點(diǎn)的閉包;知道Ia和Ib列都在I列中出現(xiàn)為止。如下表4.2.1所示： 表4.2.1狀態(tài)轉(zhuǎn)換矩陣 I Ia Ib X,1 2,3,Y 2,3,Y 2,3,Y對表4.2.1的狀態(tài)轉(zhuǎn)換矩陣進(jìn)行重新命名，令A(yù)=X,1，B=2,3,Y，轉(zhuǎn)換結(jié)果如下表4.2.2所示： 表4.2.2重命名的狀態(tài)轉(zhuǎn)換矩陣 I Ia Ib A B

11、 B B 表4.2.2相對應(yīng)的 DFA狀態(tài)轉(zhuǎn)換圖為下圖圖4.2-2所示： 圖4.2-2 DFA狀態(tài)圖結(jié)果與分析（可以加頁）： 1.對于下圖1中的NFA： 圖1 NFA狀態(tài)圖2. 輸入圖1中NFA的各邊信息：如下截圖 圖2所示： 圖2 輸入各邊信息截圖3. 對于圖1的NFA狀態(tài)轉(zhuǎn)換矩陣和重命名后的狀態(tài)矩陣如下截圖圖3所示： 圖3 DFA狀態(tài)矩陣截圖4. 將圖3中的狀態(tài)矩陣圖最小化，如下截圖圖4所示： 圖4 最小化的DFA5.根據(jù)圖4最小化的DFA狀態(tài)轉(zhuǎn)換矩陣，畫出DFA狀態(tài)轉(zhuǎn)換圖，如下圖 圖5所示： 圖5 DFA狀態(tài)裝換圖設(shè)計(jì)體會(huì)與建議： 編譯原理是一門重要但難學(xué)的課程，因?yàn)榫幾g原理是關(guān)于編寫編

12、譯器的技術(shù)，編譯器的編寫一直被認(rèn)為是十分困難的事情，所以這次選到課程設(shè)計(jì)的課題就有些無從下手的感覺，感覺任務(wù)挺艱巨的。設(shè)計(jì)要求從理論上就不太好理解，不像以前的設(shè)計(jì)編寫一個(gè)應(yīng)用程序?qū)崿F(xiàn)常見的功能，這次的課程設(shè)計(jì)注重各種算法的實(shí)現(xiàn)，比如用子集法實(shí)現(xiàn)不確定的有限自動(dòng)機(jī)的確定化、又能夠分割法實(shí)現(xiàn)確定的有限自動(dòng)機(jī)的最小化。課題雖然感覺難懂了一些，但我想不管結(jié)果如何，只要自己努力，盡力了就行。小組各成員始終相信“世上無難事，只怕有心人”。由于課程設(shè)計(jì)有幾周的時(shí)間，時(shí)間很充裕，所以這在這幾周設(shè)計(jì)中，我們小組團(tuán)結(jié)合作，互幫互助，大家都感覺這幾周過的非常充實(shí)，盡管累了點(diǎn)。同時(shí)通過這次課程設(shè)計(jì)我們深深地感覺到團(tuán)隊(duì)

13、的力量，深深體會(huì)到“團(tuán)結(jié)就是力量”。當(dāng)我們開始困惑無從下手時(shí)，我們你一句我一句的意見很快讓我們找到了前進(jìn)的方向。當(dāng)自己遇到疑難時(shí)，和組員一起討論解決了問題感覺非常欣慰，無助和孤獨(dú)感也頓時(shí)消失。通過這次課程設(shè)計(jì)給我另一個(gè)很大的體會(huì)是：流程圖的重要性。說實(shí)話，每次不管是課程設(shè)計(jì)報(bào)告還是實(shí)習(xí)報(bào)告，我們最害怕做的就是畫流程圖，所以每次報(bào)告中能省則省。而這次發(fā)現(xiàn)根據(jù)系統(tǒng)需實(shí)現(xiàn)的功能和算法畫出流程圖后，就很清楚地知道我們的程序需要哪些模塊，每個(gè)模塊需要實(shí)現(xiàn)什么功能。所以在我們以后的學(xué)習(xí)中我們不能畏懼畫流程圖，我們要積極鍛煉我們畫流程圖的能力，從而來幫助我們提高編程的能力。每次的課程設(shè)計(jì)，和以前的相比，我發(fā)

14、現(xiàn)了自己的一次又一次的進(jìn)步，因?yàn)樵降阶詈螅綍?huì)發(fā)現(xiàn)自己的不足，就會(huì)想著怎樣去改進(jìn)，怎樣去完善自己的系統(tǒng)，所以每學(xué)期的課程設(shè)計(jì)是很必要的，因?yàn)槲以谶@些過程中都學(xué)到了很多知識(shí)。附源代碼：#include#include#define MAXS 100using namespace std;string NODE; /結(jié)點(diǎn)集合string CHANGE; /終結(jié)符集合int N; /NFA邊數(shù)struct edge string first; string change; string last; ;struct chan string ltab; string jiheMAXS; ;void ko

15、ng(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+) for(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

16、; 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(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

17、; 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,n,h,x,y,len; bool flag; string jhMAXS,endnode,ednode,sta; cout請輸入NFA各邊信息（起點(diǎn) 條件空為* 終點(diǎn)），以#結(jié)束：endl; for(i=0;ibi.first; if(bi.first=#) break; cinbi.changebi.last;

18、N=i; for(i=0;iNODE.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)的是：endnode; for(i=0;iNODE.length() cout所輸終態(tài)不在集合中，錯(cuò)誤！endl; return; chan *t=new chanMAXS; t0.ltab=b0.

19、first; h=1; eclouse(b0.first0,t0.ltab,b); /求e-clouse for(i=0;ih;i+) for(j=0;jti.ltab.length();j+) for(m=0;mlen;m+) eclouse(ti.ltabj,ti.jihem,b); /求e-clouse for(k=0;klen;k+) move(ti,k,b); /求move(I,a) for(j=0;jti.jihek.length();j+) eclouse(ti.jihekj,ti.jihek,b); /求e-clouse for(j=0;jlen;j+) paixu(ti.ji

20、hej); /對集合排序以便比較 for(k=0;kh;k+) flag=operator=(tk.ltab,ti.jihej); if(flag) break; if(!flag&ti.jihej.length() th+.ltab=ti.jihej; coutendl狀態(tài)轉(zhuǎn)換矩陣如下：endl; outputfa(len,h,t); /輸出狀態(tài)轉(zhuǎn)換矩陣 /狀態(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;

21、 NODE+=ti.ltab; coutsta=ti.ltabendl; for(j=0;jendnode.length();j+) if(sta.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); /輸出DFA cout其中終態(tài)為：endnodeendl; /DFA最小化 m=2; sta.erase(); flag=0; for(i=0;im;i+) for(k=0;klen;k+) 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.l