安徽大學(xué)編譯原理試驗(yàn)斯

1、不確定的有窮自動機(jī)的化簡2015年11月25日星期三班級： 軟件工程 學(xué)號： E21314003 姓名： 李世1. 目的與要求 通過設(shè)計(jì)、編寫和調(diào)試，將不確定的有窮自動機(jī)轉(zhuǎn)換為與之等價(jià)的確定的有窮自動機(jī)的程序，使學(xué)生了解子集法。掌握轉(zhuǎn)換過程中的相關(guān)概念和方法。DFA的表現(xiàn)形式可以是表格或圖形。 2. 理論基礎(chǔ)有窮自動機(jī)(也稱有限自動機(jī))作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)式所表示的集合. 應(yīng)用有窮自動機(jī)這個(gè)理論，為詞法分析程序的自動構(gòu)造尋找有效的方法和工具。有窮自動機(jī)分為兩類，即，確定的有窮自動機(jī)(Deterministic Finite Automata)和不確定的有窮自動機(jī)(

2、Nondeterministic Finite Automata) 。(1) 不確定的有窮自動機(jī)的定義： 一個(gè)不確定的有窮自動機(jī)（NFA）M是一個(gè)五元組： NFA M=K，f，S，Z， 其中: K為狀態(tài)的有窮非空集; 為有窮輸入字母表; f為K× * 到K的子集（2K）的一種映射, 2K表示K的冪集（f不是一個(gè)單值函數(shù)）; SK是初始狀態(tài)集; Z K為終止?fàn)顟B(tài)集. 例子: NFA M=（S，P，Z，0，1，f，S，P，Z），其中： f（S，0）=P/函數(shù)的結(jié)果為集合f（S，1）=S，Z f（P，1）=Z f（Z，0）=P f（Z，1）=P 狀態(tài)圖表示為： 矩陣表示為： (2) 確定的

3、有窮自動機(jī)的定義： 一個(gè)確定的有窮自動機(jī)（DFA）M是一個(gè)五元組：M=(K，f，S，Z) 其中: K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)； 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號，所以也稱為輸入符號表； f是轉(zhuǎn)換函數(shù)，是在K×K上的映射，即，如f（ki，a）=kj，(kiK，kjK)就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)； SK是唯一的一個(gè)初態(tài)； Z K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。例子:DFA M=（S，U，V，Q，a，b，f，S，Q），其中f定義為： f（S，a）=U f（V，a）=U f（S，b）

4、=V f（V，b）=Q f（U，a）=Q f（Q，a）=Q f（U，b）=V f（Q，b）=Q 狀態(tài)圖表示為：矩陣表示為：(3) 確定有限自動機(jī)和不確定有限自動機(jī)DFA是NFA的特例。對每個(gè)NFA N一定存在一個(gè)DFA ，使得L(M)=L(N)。對每個(gè)NFA N存在著與之等價(jià)的DFA M。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法. 子集法的基本思想：讓DFA的每一個(gè)狀態(tài)對應(yīng)NFA的一組狀態(tài)，也就是讓DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號后可能達(dá)到的所有狀態(tài)。注意：與某一NFA等價(jià)的DFA不唯一. a) 定義對狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算： 狀態(tài)集合I的-閉包：表

5、示為-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達(dá)的狀態(tài)的集合。 狀態(tài)集合I中的任何狀態(tài)S都屬于-closure(I)。狀態(tài)集合I的a弧轉(zhuǎn)換：表示為move(I, a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。三、調(diào)試測試四、程序源代碼#include<iostream> #include<string> #define MAXS 100 using namespace std; string NODE; string CHANGE; int N; struct edge string fir

6、st; string change; string last; ; struct chan string ltab; string 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; a

7、i+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="*") 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+

8、) for(j=0;j<N;j+) if(CHANGEm=bj.change0)&&(he.ltabi=bj.first0) if(he.jihem.find(bj.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

9、; /輸出 void outputfa(int len,int h,chan *t) int i,j,m; cout<<" I " for(i=0;i<len;i+) cout<<'I'<<CHANGEi<<" " cout<<endl<<"-"<<endl; for(i=0;i<h;i+) cout<<' '<<ti.ltab; m=ti.ltab.length(); for(j=0

10、;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,x,y,len; bool flag; string jhMAXS,endnode,ednode,sta; cout<<"*"<<endl;cout<<"* 頁式地址重定位模擬 *"<<endl;cout<<"* 作者

11、：李世 E21314003 *"<<endl;cout<<"* 13級軟件工程 *"<<endl;cout<<"*"<<endl;cout<<"請輸入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;

12、N=i; /*for(j=0;j<N;j+) cout<<bj.first<<bj.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!="*&quo

13、t;) CHANGE+=bi.change; len=CHANGE.length(); cout<<"結(jié)點(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<<

14、;endl; chan *t=new chanMAXS; t0.ltab=b0.first; h=1; eclouse(b0.first0,t0.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-clouse for(k=0;k<len;k+) /cout<<ti.jihek<<"-&

15、gt;" move(ti,k,b); /求move(I,a) /cout<<ti.jihek<<endl; for(j=0;j<ti.jihek.length();j+) eclouse(ti.jihekj,ti.jihek,b); /求e-clouse for(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(

16、) 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; 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&

17、lt;<''<<sta<<"="<<ti.ltab<<endl; for(j=0;j<endnode.length();j+) 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)>

18、;ednode.length() d0+=NODEi; endnode=ednode; cout<<endl<<"DFA如下："<<endl; outputfa(len,h,t); /輸出DFA cout<<"其中終態(tài)為："<<endnode<<endl; /DFA最小化 m=2; sta.erase(); flag=0; for(i=0;i<m;i+) /cout<<"d"<<i<<"="<&l

19、t;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.find(dij).jihek)<dn.length()|tNODE.find(dij).jihek.length()=0) if(tNODE.find(dij).jihek.length()=0) x=m; else x=n; if(!sta.length() s

20、ta+=x+48; else if(sta0!=x+48) dm+=dij; flag=1; di.erase(j,1); /cout<<di<<endl; j-; break; /跳出n /n /j if(flag) m+; flag=0; /cout<<"sta="<<sta<<endl; sta.erase(); /k /i cout<<endl<<"集合劃分：" for(i=0;i<m;i+) cout<<""<<di<<" " cout<<endl; /狀態(tài)重新命名 chan *md=new chanm; NODE.erase(); cout<<endl<<&qu