編譯原理課程設(shè)計

編譯原理課程實踐報告設(shè)計名稱：NFA轉(zhuǎn)化為DFA的轉(zhuǎn)換算法及實現(xiàn)二級學(xué)院：數(shù)學(xué)與計算機科學(xué)學(xué)院專業(yè)：計算機科學(xué)與技術(shù)班級：計科本091班名：學(xué)號：指導(dǎo)老師：日期：2012年6月摘要確定有限自動機確定的含義是在某種狀態(tài)，面臨一個特定的符號只有一個轉(zhuǎn)換，進入唯一的一個狀態(tài)。不確定的有限自動機則相反，在某種狀態(tài)下，面臨一個特定的符號是存在不止一個轉(zhuǎn)換，即是可以允許進入一個狀態(tài)集合。在非確定的有限自動機NFA中，由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。這種不確定性給識別過程帶來的反復(fù)，無疑會影響到FA的工作效率。而DFA則是確定的，將NFA轉(zhuǎn)化為DFA將大大提高工作效率，因此將NFA轉(zhuǎn)化為DFA是有其一定必要的。對于任意的一個不確定有限自動機（NFA）都會存在一個等價的確定的有限自動機（DFA），即L（N）=L（M）。本文主要是介紹如何將NFA轉(zhuǎn)換為與之等價的簡化的DFA，通過具體實例，結(jié)合圖形，詳細說明轉(zhuǎn)換的算法原理。關(guān)鍵詞：有限自動機；確定有限自動機（DFA），不確定有限自動機（NFA）AbstractFiniteautomataisdeterminateandindeterminatetwoclass.Determinethemeaningisinacertainstate,facesaparticularsymbolonlyoneconversion,enteronlyonestate.Notdeterministicfiniteautomataistheopposite,inacertainstate,facesaparticularsymbolisthepresenceofmorethanoneconversion,thatistobeallowedtoenterastateset.NondeterministicfinitestateautomataNFA,becauseofsomestatearetransferredfromanumberofpossiblefollow-upstatearechosen,soaNFAsymbolstringrecognitionmustbeatrialprocess.Thisuncertaintytotherecognitionprocessbroughtaboutbyrepeated,willundoubtedlyaffecttheefficiencyoftheFA.WhiletheDFAisdetermined,convertingNFAtoDFAwillgreatlyimprovetheworkingefficiency,thusconvertingNFAtoDFAisitsnecessary.Foranyanondeterministicfiniteautomaton(NFA)canbeanequivalentdeterministicfiniteautomaton(DFA),L(N)=L(M).ThispapermainlyintroduceshowtoconvertNFAtoequivalentsimplifiedDFA,throughconcreteexamples,combinedwithgraphics,adetaileddescriptionofthealgorithmprincipleofconversion.Keywords::finiteautomata;deterministicfiniteautomaton(DFA),nondeterministicfiniteautomaton(NFA目錄TOC\o"1-5"\h\z\o"CurrentDocument"前言：1\o"CurrentDocument"1.1背景11.2實踐目的1\o"CurrentDocument"1.2課程實踐的意義1\o"CurrentDocument"NFA和DFA的概念22.1不確定有限自動機NFA22.2確定有限自動機DFA3\o"CurrentDocument"3.從NDF到DFA的等價變化步驟53.1轉(zhuǎn)換思路53.2.消除空轉(zhuǎn)移53.3子集構(gòu)造法7\o"CurrentDocument"4程序?qū)崿F(xiàn)94.1程序框架圖94.2數(shù)據(jù)流程圖94.3實現(xiàn)代碼104.4運行環(huán)境10\o"CurrentDocument"4.5程序?qū)崿F(xiàn)結(jié)果10\o"CurrentDocument"用戶手冊12\o"CurrentDocument"課程總結(jié)：12\o"CurrentDocument"參考文獻12\o"CurrentDocument"附錄131.前言:1.1背景有限自動機作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。有限自動機(FiniteAutomate)是用來模擬實物系統(tǒng)的數(shù)學(xué)模型，它包括如下五個部分：?有窮狀態(tài)集States輸入字符集Inputsymbols轉(zhuǎn)移函數(shù)Transitions起始狀態(tài)Startstate接受狀態(tài)Acceptingstate(s)1.2實踐目的設(shè)計、編制、調(diào)式一個有窮自動機程序，加深對NFA轉(zhuǎn)換為DFA的原理的理解。掌握NFA確定化的過程。1.2課程實踐的意義通過本課程設(shè)計教學(xué)所可以使我們充分理解和掌握NFA，DFA以及NFA確定化過程的相關(guān)概念和知識，理解和掌握子集法的相關(guān)知識和應(yīng)用，編程實現(xiàn)對輸入NFA轉(zhuǎn)換成DFA輸出的功能。2.NFA和DFA的概念2.1不確定有限自動機NFANFA(nondeterministicfinite-stateautomata)即非確定有限自動機，一個非確定的有限自動機NFAM’是一個五元式：NFAM’=(S,SU{e),5,S0,F)其中S一有限狀態(tài)集，SU{E}一輸入符號加上8,即自動機的每個結(jié)點所射出的弧可以是習(xí)中一個字符或是8.S0—初態(tài)集F一終態(tài)集5—轉(zhuǎn)換函數(shù)SX2U{8}-2S(2S--S的幕集一S的子集構(gòu)成的集合)例1：NFAM=({S,P,Z},{0,1},f,{s,p},{z})其中f(s,0)={p}f(z,0)={p}f(p,1)={z}f(z,1)={p}f(s,1)={s,z}①NFA的狀態(tài)圖表示如下：②NFA矩陣表示:狀態(tài)'滓符0狀態(tài)'滓符0SPP{}ZP1S,Z0Z0P12.2確定有限自動機DFADFA(deterministicfinite-stateautomata)即確定有限自動機，一個確定的有限自動機DFAM是一個五元式：M=(S,S,5,S0,Z)其中:S—有限狀態(tài)集習(xí)一輸入字母表5一映射函數(shù)(也稱狀態(tài)轉(zhuǎn)換函數(shù))SX一S5(s,a)=S’，S,S’eS,a^ES0一初始狀態(tài)SOeSZ一終止狀態(tài)集ZS例2：DFAM=({S,U,V,Q},{a,b},f,s,{Q})其中f的定義為：f(S,a)=Uf(S,b)=Vf(U,a)=Qf(U,b)=Vf(V,a)=Uf(V,b)=Qf(Q,a)=Qf(Q,b)=Q①DFA的狀態(tài)圖表示：假如DFAM含有m個狀態(tài)，n個輸入符，那么這個狀態(tài)含有m個節(jié)點，每個節(jié)點最多有n個孤射出，整個圖整個圖含有唯一一個初態(tài)結(jié)點和若干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“二＞”或標以“-”，終態(tài)結(jié)點用雙圈表示或標以“+”，若f(ki,a)=kj，則從狀態(tài)結(jié)點ki到狀結(jié)點kj畫標記為a的孤：②DFA矩陣表示：一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭二＞標明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標以1，非終態(tài)標以0.

狀M，字符aSUUQVUQQbV0狀M，字符aSUUQVUQQbV0V0Q0Q1事實已經(jīng)證明了不管是非確定的有限自動機M還是具有8-轉(zhuǎn)移的非確定的有限自動機，都可以找到一個與之等價的確定有限自動機，使得L(M)=L(M’)。3.1轉(zhuǎn)換思路由非確定的有限自動機出發(fā)構(gòu)造與之等價的確定的有限自動機的辦法是確定的有限自動機的狀態(tài)對應(yīng)于非確定的有限自動機的狀態(tài)集合，即要使轉(zhuǎn)換后的DFA的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài)。該DFA使用它的狀態(tài)去記錄在NFA讀入一個輸入符號后可能到達的所有狀態(tài)，也就是說，在讀入符號串a(chǎn)1a2a3???an之后，該DFA處在這樣一個狀態(tài)，該狀態(tài)表示這個NFA的狀態(tài)的一個子集T，而T是從NFA的開始狀態(tài)沿著某個標記為a1a2a3???an的路徑可以到達的那些狀態(tài)。3.2.消除空轉(zhuǎn)移.消除N形式的產(chǎn)生式，即消除空轉(zhuǎn)移。狀態(tài)集合I的a孤轉(zhuǎn)換Ia:定義為一狀態(tài)集，是指從狀態(tài)集I出發(fā)先經(jīng)過a孤后再經(jīng)過若干條8孤而能到達的狀態(tài)的集合?？梢詫懽鳎篒a=e-closure(J)，J=move(I,a)，其中，J是從I中任一狀態(tài)出發(fā)經(jīng)過一條a孤到達的狀態(tài)集合，記為move(I,a)。

s表示NFA的狀態(tài)，T表示NFA的狀態(tài)集合，a表示一個inputsymbole-transition（e轉(zhuǎn)換）就是說inputsymbol為e時的transition（轉(zhuǎn)換）操作(operation)描述(description)e-closure(s)從NFA的狀態(tài)s出發(fā)，只通過e-transition到達的NFA的狀態(tài)集合e-closure(T)NFA的集合T中的狀態(tài)p，只通過e-transition到達的NFA的狀態(tài)集合，再求這些集合的交集。用數(shù)學(xué)表達就是（p|p屬于e-closure（t）,t屬于T}||move(T,a)NFA的集合，這個集合在inputsymbol為a，狀態(tài)為T中任意狀態(tài)情況下，通過一個轉(zhuǎn)換得到的集合例如：對于以下狀態(tài)圖中：e-closure({0})={0,1,2,4,7}在這里設(shè)I={0,1,2,4,7}，則因為有move(I,a)={3,8}=J,所以Ia=e-closure(J)=e-closure({3,8})={1,2,3,4,6,7,8}e

3.3子集構(gòu)造法確定化每個多重轉(zhuǎn)移，即拆分多值函數(shù)為單位函數(shù)，具體轉(zhuǎn)換，采用子集構(gòu)造法。以下面的基于字母表￡={a,b}上的具有^-轉(zhuǎn)移的非確定有限自動機M為例。步驟1：以I,Ia、Ib等為列做表，其中I列第一行的內(nèi)容是初態(tài)的8-閉包所得到的狀態(tài)集合。并以此為I計算Ia、Ib等，而且在所計算出的Ia、Ib等中若有新的狀態(tài)集產(chǎn)生，就重復(fù)以此新的集合為I再此計算Ia、Ib等，直到在所得的Ia、Ib等中不再產(chǎn)生新的狀態(tài)集為止。IIaIb{x,5,1}{5,1,3}{5,1,4}{5,1,3}{5,1,3,2,6,y}{5,1,4}{5,1,4}{5,1,3}{5,1,4,2,6,y}{5,1,3,2,6,y}{5,1,3,2,6,y}{5,1,4,6,y}{5,1,4,2,6,y}{5,1,3,6,y}{5,1,4,2,6,y}{5,1,4,6,y}{5,1,3,6,y}{5,1,4,2,6,y}{5,1,3,6,y}{5,1,3,2,6,y}{5,1,4,6,y}

步驟2：在上表中將原NFA初態(tài)的e-閉包作為轉(zhuǎn)換后的DFA的初態(tài)，包含原NFA終態(tài)的狀態(tài)作為轉(zhuǎn)換后的DFA的終態(tài)，并進行重新編號得到轉(zhuǎn)換后的DFA的狀態(tài)轉(zhuǎn)移矩陣如下：ab{x,5,1}1{5,1,3}2{5,1,4}30{5,1,3}2{5,1,3,2,6,y}4{5,1,4}30{5,1,4}3{5,1,3}2{5,1,4,2,6,y}0{5,1,3,2,6,y}4{5,1,3,2,6,y}4{5,1,4,6,y}6{5,1,4,2,6,y}5{5,1,3,6,y}7{5,1,4,2,6,y}15{5,1,4,6,y}6{5,1,3,6,y}7{5,1,4,2,6,y}15{5,1,3,6,y}7{5,1,3,2,6,y}4{5,1,4,6,y}6步驟3：畫出轉(zhuǎn)換后的DFA的狀態(tài)圖:b4.1程序框架圖4.2數(shù)據(jù)流程圖4程序?qū)崿F(xiàn)NFA轉(zhuǎn)化為N

F

A

圖

結(jié)

構(gòu)NFA狀態(tài)表4.3實現(xiàn)代碼（見附錄）4.4運行環(huán)境開發(fā)平臺：MicrosoftvisualC++6.0運行平臺：Windowsxp/Windows20004.5程序?qū)崿F(xiàn)結(jié)果實現(xiàn)NFA例題為：NFAM=({S,P,Z},{0,1},f,{s,p},{z})

其中f(z,0)={p}f(s,1)=f(z,0)={p}f(s,1)={s,z}f(p,1)={z}f(z,1)={p}根據(jù)例題輸入NFA各邊的信息得出結(jié)果如下圖:情輸入NFH各邊信息-分別為：起點條件［空為刁終點，最后以K結(jié)束：S0pB0pH)12QlpE1Ssis結(jié)點中屬于終態(tài)的-2曰狀態(tài)轉(zhuǎn)換矩陣如下■I10II——SVS2V2szpspz2VPspzpspzM命名:<s>=Akp>=BksE>=cSpH>=E疏如下:IISII——ABcEDCBEDBBEB柱中終態(tài)為:CDEE集合劃分:3)<CE^<B><?>屋命名:<A>=A<CE>=B<BJ=Cp>=D屈小化D?如下：IIQII——ACBBCBCDDCC用戶手冊本程序應(yīng)在MicrosoftVisualC++6.0下運行。NFA的確定化是編譯過程中一個重要的部分，由于本程序的輸入很多，而且有多種格式的輸入，所以輸入時必須非常小心細致。對于狀態(tài)轉(zhuǎn)換矩陣的表示，冒號前的是新狀態(tài)名，冒號后的是舊狀態(tài)名。對于轉(zhuǎn)化后的DFA表示，3個數(shù)據(jù)分別表示為起始狀態(tài)、接受字符和到達狀態(tài)，例如（0,1,1）表示為新狀態(tài)0接受字符1到達新字符狀態(tài)1。運行結(jié)果因為轉(zhuǎn)換字符輸入順序的不同，得出的結(jié)果有可能與筆算得出的順序有所不同，但是結(jié)果依然是正確。課程總結(jié):通過這次課程實踐設(shè)計，讓我對課堂上老師所講到的不確定和確定有限自動機有了更深的理解，理解了它們的構(gòu)造和怎樣相互轉(zhuǎn)化。很好的理解了子集法的演算過程。經(jīng)過多次試驗，在正確輸入相關(guān)數(shù)據(jù)的情況下，程序能正常運行，當錯誤操作或輸入錯誤數(shù)據(jù)時，程序?qū)?yīng)錯誤自動關(guān)閉。經(jīng)過這次課程設(shè)計，也讓我深刻的認識到實踐才是最重要的。書本只能教給我們基礎(chǔ)知識，要怎樣運用，將那些知識真正吸收，轉(zhuǎn)化為自己的智慧，只有通過實踐才能達到。編譯原理是一門實用性很強，對我們的專業(yè)很有幫助的科目，我將會繼續(xù)努力，不斷增加自己的知識面，把編譯原理學(xué)習(xí)的更好。同時我也發(fā)現(xiàn)自己對于有限自動機的知識掌握得還不是很多，在這次課程實踐中，我懂得了怎樣去和別人交流，更好地掌握和熟練了所學(xué)的知識。參考文獻（1）楊路明、郭浩志.C語言程序設(shè)計教程.2003年12月第1版.北京:北京郵電大學(xué)出版社.2005（2）陳火旺.程序設(shè)計語言編譯原理.2000年1月第3版.北京：國防工業(yè)出版社.2006.46-51（3）嚴蔚敏、吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.1997年4月第1版.北京:清華大學(xué)出版社.2005（4）王曉東編著.計算機算法設(shè)計與分析.電子工業(yè)出版社.20048.附錄NFA轉(zhuǎn)換為DFA采用C++編程實現(xiàn)代碼如下#include<iostream>#include<string>#defineMAXS100usingnamespacestd;stringNODE;//結(jié)點集合stringCHANGE;//終結(jié)符集合intN;//NFA邊數(shù)structedge(stringfirst;stringchange;stringlast;};structchan(stringltab;stringjihe[MAXS];};voidkong(inta)(inti;for(i=0;i<a;i++)cout<<'';}〃排序voidpaixu(string&a)(inti,j;charb;for(j=0;j<a.length();j++)for(i=0;i<a.length();i++)if(NODE.find(a[i])>NODE.find(a[i+1]))(b=a[i];a[i]=a[i+1];a[i+1]=b;}}voideclouse(charc,string&he,edgeb[])(intk;for(k=0;k<N;k++)(if(c==b[k].first[0])if(b[k].change=二〃*〃)(if(he.find(b[k].last)>he.length())he+=b[k].last;eclouse(b[k].last[0],he,b);}}}voidmove(chan&he,intm,edgeb[])(inti,j,k,l;k=he.ltab.length();l二he.jihe[m].length();for(i=0;i<k;i++)for(j=0;j<N;j++)if((CHANGE[m]==b[j].change[0])&&(he.ltab[i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())he.jihe[m]+=b[j].last[0];for(i=0;i<l;i++)for(j=0;j<N;j++)if((CHANGE[m]==b[j].change[0])&&(he.jihe[m][i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())he.jihe[m]+=b[j].last[0];}〃輸出voidoutputfa(intlen,inth,chan*t)(inti,j,m;cout<<"I";for(i=0;i<len;i++)cout<<'I'<<CHANGE[i]<<〃";cout<<endl<<""<<endl;for(i=0;i<h;i++)(cout<<''<<t[i].ltab;m=t[i].ltab.length();for(j=0;j<len;j++)(kong(8-m);m=t[i].jihe[j].length();cout<<t[i].jihe[j];}cout<<endl;}}voidmain()(edge*b=newedge[MAXS];inti,j,k,m,n,h,x,y,len;boolflag;stringjh[MAXS],endnode,ednode,sta;cout<<"請輸入NFA各邊信息,分別為：起點條件[空為*]終點，最后以#結(jié)束:"<<endl;for(i=0;i<MAXS;i++)(cin>>b[i].first;if(b[i].first==〃#〃)break;cin>>b[i].change>>b[i].last;}N=i;/*for(j=0;j<N;j++)cout<<b[j].first<<b[j].change<<b[j].last<<endl;*/for(i=0;i<N;i++)(if(NODE.find(b[i].first)>NODE.length())NODE+=b[i].first;if(NODE.find(b[i].last)>NODE.length())NODE+=b[i].last;if((CHANGE.find(b[i].change)>CHANGE.length())&&(b[i].change!二〃*〃))CHANGE+=b[i].change;}len=CHANGE.length();cout<<〃結(jié)點中屬于終態(tài)的是：〃<<endl;

cin>>endnode;for(i=0;i<endnode.length();i++)if(NODE.find(endnode[i])>NODE.length())(cout<<"所輸終態(tài)不在集合中，錯誤！"<<endl;return;}//cout<<"endnode="<<endnode<<endl;chan*t=newchan[MAXS];t[0].ltab=b[0].first;h=1;eclouse(b[0].first[0],t[0].ltab,b);//求e-clouse//cout<<t[0].ltab<<endl;for(i=0;i<h;i++)(for(j=0;j<t[i].ltab.length();j++)for(m=0;m<len;m++)eclouse(t[i].ltab[j],t[i].jihe[m],b);//求e-clousefor(k=0;k<len;k++)(//cout<<t[i].jihe[k]<<"->";move(t[i],k,b);//求move(I,a)//cout<<t[i].jihe[k]<<endl;for(j=0;j<t[i].jihe[k].length();j++)eclouse(t[i].jihe[k][j],t[i].jihe[k],b);//求e-clouse}for(j=0;j<len;j++)(paixu(t[i].jihe[j]);for(k=0;k<h;k++)//paixu(t[i].jihe[j]);for(k=0;k<h;k++)flag=operator==(t[k].ltab,t[i].jihe[j]);if(flag)break;}if(!flag&&t[i].jihe[j].length())t[h++].ltab=t[i].jihe[j];}}cout<<endl<<"狀態(tài)轉(zhuǎn)換矩陣如下："<<endl;outputfa(len,h,t);//輸出狀態(tài)轉(zhuǎn)換矩陣//狀態(tài)重新命名string*d=newstring[h];NODE.erase();cout<<endl<<"重命名："<<endl;for(i=0;i<h;i++)(sta=t[i].ltab;t[i].ltab.erase();t[i].ltab='A'+i;NODE+=t[i].ltab;cout<<'('<<sta<<"}="<<t[i].ltab<<endl;for(j=0;j<endnode.length();j++)if(sta.find(endnode[j])<sta.length())d[1]=ednode+=t[i].ltab;for(k=0;k<h;k++)for(m=0;m<len;m++)if(sta==t[k].jihe[m])t[k].jihe[m]=t[i].ltab;for(i=0;i<NODE.length();i++)if(ednode.find(NODE[i])>ednode.length())d[0]+=NODE[i];endnode=ednode;cout<<endl<<"DFA如下："<<endl;outputfa(len,h,t);〃輸出DFAcout<<〃其中終態(tài)為："<<endnode<<endl;//DFA最小化m=2;sta.erase();flag=0;for(i=0;i<m;i++)(//cout<<"d["<<i<<"]="<<d[i]<<endl;for(k=0;k<len;k++)(//cout<<〃I〃<<CHANGE[k]