實(shí)驗(yàn)四有窮自動(dòng)機(jī)的確定化

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)四：有窮狀態(tài)自動(dòng)機(jī)的確定化實(shí)驗(yàn)?zāi)康模?. 熟練掌握DFA及NFA的定義及有關(guān)概念。2. 理解并掌握確定的有窮自動(dòng)機(jī)的化簡(jiǎn)等算法。實(shí)驗(yàn)要求：1.輸入： 非確定有限（窮）狀態(tài)自動(dòng)機(jī)。2.輸出： 確定化的有限（窮）狀態(tài)自動(dòng)實(shí)驗(yàn)原理：1.由定義可見，不確定有限自動(dòng)機(jī)NFA與確定有限自動(dòng)機(jī)DFA的主要區(qū)別是：（1）NFA的初始狀態(tài)S為一個(gè)狀態(tài)集，即允許有多個(gè)初始狀態(tài)；（2）NFA中允許狀態(tài)在某輸出邊上有相同的符號(hào)，即對(duì)同一個(gè)輸入符號(hào)可以有多個(gè)后繼狀態(tài)。即DFA中的F是單值函數(shù)，而NFA中的F是多值函數(shù)。2. NFA確定化為DFA同一個(gè)字符串可以由多條通路產(chǎn)生

2、，而在實(shí)際應(yīng)用中，作為描述控制過(guò)程的自動(dòng)機(jī)，通常都是確定有限自動(dòng)機(jī)DFA，因此這就需要將不確定有限自動(dòng)機(jī)轉(zhuǎn)換成等價(jià)的確定有限自動(dòng)機(jī)，這個(gè)過(guò)程稱為不確定有限自動(dòng)機(jī)的確定化，即NFA確定化為DFA。下面介紹一種NFA的確定化算法，這種算法稱為子集法：（1）若NFA的全部初態(tài)為S1，S2，Sn，則令DFA的初態(tài)為：SS1，S2，Sn，其中方括號(hào)用來(lái)表示若干個(gè)狀態(tài)構(gòu)成的某一狀態(tài)。（2）設(shè)DFA的狀態(tài)集K中有一狀態(tài)為Si，Si+1，Sj，若對(duì)某符號(hào)a，在NFA中有F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 則令F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 為DFA的一個(gè)轉(zhuǎn)換

3、函數(shù)。若 Si，Si+1，Sk 不在K中，則將其作為新的狀態(tài)加入到K中。（3）重復(fù)第2步，直到K中不再有新的狀態(tài)加入為止。（4）上面得到的所有狀態(tài)構(gòu)成DFA的狀態(tài)集K，轉(zhuǎn)換函數(shù)構(gòu)成DFA的F，DFA的字母表仍然是NFA的字母表。（5）DFA中凡是含有NFA終態(tài)的狀態(tài)都是DFA的終態(tài)。3. NFA確定化的實(shí)質(zhì)是以原有狀態(tài)集上的子集作為DFA上的一個(gè)狀態(tài)，將原狀態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有限自動(dòng)機(jī)確定化。經(jīng)過(guò)確定化后，狀態(tài)數(shù)可能增加，而且可能出現(xiàn)一些等價(jià)狀態(tài)，這時(shí)就需要簡(jiǎn)化。實(shí)驗(yàn)內(nèi)容：1.程序代碼如下：#include#include#includeusing namespace s

4、td;#define max 100struct edge string first;/邊的初始結(jié)點(diǎn)string change;/邊的條件string last;/邊的終點(diǎn);int N;/NFA的邊數(shù)vector value;/求狀態(tài)集合I的&-閉包，用&代替“空“string closure(string a,edge *b)int i,j;for(i=0;ia.length();i+)for(j=0;jN;j+)if(bj.first0=ai&bj.change=&)a=a+bj.last0;return a;/狀態(tài)集合I的a弧轉(zhuǎn)換string move(string jihe,char

5、ch,edge *b)int i,j;string s=;for(i=0;ijihe.length();i+) for(j=0;jN;j+)if(bj.first0=jihei&bj.change0=ch) s=s+bj.last;return s;string sort(string t)int k,i,j;char tt;for(i=0;it.length()-1;i+)k=i;for(j=i+1;jt.length();j+)if(tjtk)k=j;tt=tk;tk=ti;ti=tt;return t;void main() int i,j,x=0,h,length,m,d=0; str

6、ing Change;/輸入符號(hào) string First,Last;/初態(tài)，終態(tài)， string Tmax,ss; edge *b=new edgemax; cout請(qǐng)輸入各邊信息：起點(diǎn) 條件（空用&表示） 終點(diǎn)，以輸入#結(jié)束。endl; for(i=0;ibi.first; if(bi.first=#)break; else cinbi.changebi.last; N=i; cout請(qǐng)輸入該NFA的初態(tài)及終態(tài)：FirstLast; cout請(qǐng)輸入此NFA狀態(tài)中的輸入符號(hào)即邊上的條件:Change; Tx=closure(First,b); Tx=sort(Tx); value.push_

7、back(0); i=0; while(valuei=0&value.size() valuei=1; for(j=0;jChange.length();j+) ss=; ss=move(Ti,Changej,b); length=value.size(); for(h=0;hlength;h+) if(Th=sort(closure(ss,b)break; if(h=length) T+x=sort(closure(ss,b); value.push_back(0); i+; edge *DFA=new edgemax; for(i=0;i=x;i+)/構(gòu)造DFA的各邊 for(j=0;jC

8、hange.length();j+) DFAd.first=Ti; DFAd.change=Changej; ss=; ss=sort(closure(move(Ti,Changej,b),b); for(m=0;m=x;m+) if(ss=Tm)DFAd+.last=Tm; cout此NFA構(gòu)造的DFA的各邊信息如下：endl起點(diǎn) 條件 終點(diǎn)endl; for(i=0;id;i+) for(m=0;m=x;m+) if(DFAi.first=Tm)coutm DFAi.change; for(m=0;m=x;m+) if(DFAi.last=Tm)cout mendl; cout該DFA的初態(tài)為：; for(m=0;m=x;m+) for(j=0;jTm.length();j+) ss=Tm; if(ssj=First0)coutmendl; cout該DFA的終態(tài)為：; for(m=0;m=x;m+) for(j=0;jTm.length();j+) ss=Tm; if(ssj