實(shí)驗(yàn)五DFA的最小化

1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)五：DFA的最小化實(shí)驗(yàn)?zāi)康模?. 熟練掌握DFA及NFA的定義及有關(guān)概念。2. 理解并掌握確定的有窮自動(dòng)機(jī)的最小化等算法。實(shí)驗(yàn)要求：輸入： DFA。輸出： 最小化的DFA。實(shí)驗(yàn)原理：1.化簡(jiǎn)DFA關(guān)鍵在于把它的狀態(tài)集分成一些兩兩互不相交的子集，使得任何兩個(gè)不相交的子集間的狀態(tài)都是可區(qū)分的，而同一個(gè)子集中的任何兩個(gè)狀態(tài)都是等價(jià)的，這樣可以以一個(gè)狀態(tài)作為代表而刪去其他等價(jià)的狀態(tài)，然后將無(wú)關(guān)狀態(tài)刪去，也就獲得了狀態(tài)數(shù)最小的DFA。2.DFA的化簡(jiǎn)算法：（1） 首先將DFA M的狀態(tài)劃分出終止?fàn)顟B(tài)集K1和非終止?fàn)顟B(tài)集K2。KK1K2 由上述定義知，K1和K2是不等價(jià)的。（2） 對(duì)各

2、狀態(tài)集每次按下面的方法進(jìn)一步劃分，直到不再產(chǎn)生新的劃分。設(shè)第i次劃分已將狀態(tài)集劃分為k組，即：KK1(i)K2(i)Kk(i)對(duì)于狀態(tài)集Kj(i)（j=1,2,k）中的各個(gè)狀態(tài)逐個(gè)檢查，設(shè)有兩個(gè)狀態(tài)Kj、 KjKj(i)，且對(duì)于輸入符號(hào)a，有：F（Kj'，a）KmF（Kj''，a）Kn如果Km和Kn屬于同一個(gè)狀態(tài)集合，則將Kj和Kj放到同一集合中，否則將Kj和Kj分為兩個(gè)集合。（3） 重復(fù)第（2）步，直到每一個(gè)集合不能再劃分為止，此時(shí)每個(gè)狀態(tài)集合中的狀態(tài)均是等價(jià)的。（4） 合并等價(jià)狀態(tài)，即在等價(jià)狀態(tài)集中取任意一個(gè)狀態(tài)作為代表，刪去其他一切等價(jià)狀態(tài)。（5） 若有無(wú)關(guān)狀態(tài)，

3、則將其刪去。根據(jù)以上方法就將確定有限自動(dòng)機(jī)進(jìn)行了簡(jiǎn)化，而且簡(jiǎn)化后的自動(dòng)機(jī)是原自動(dòng)機(jī)的狀態(tài)最少的自動(dòng)機(jī)。實(shí)驗(yàn)內(nèi)容：程序代碼如下：#include<iostream>#include<string>using namespace std;#define max 100struct edge string first;/邊的初始結(jié)點(diǎn)string change;/邊的條件string last;/邊的終點(diǎn);int N;/NFA的邊數(shù)string partmax;/分割子集/狀態(tài)集合I的a弧轉(zhuǎn)換string move(string jihe,char ch,edge *b)int

4、 i,j;string s=""for(i=0;i<jihe.length();i+) for(j=0;j<N;j+)if(bj.first0=jihei&&bj.change0=ch) s=s+bj.last;if(s="")return "&"else return s;/判斷子串是否存在在某一集合bool isexist(string s,string d)if(d!=""&&0<=d.find(s)&&d.find(s)<=d.

5、length()-1)return 1;else return 0;/分割子集法進(jìn)行DFA的最小化int divide(edge *b,string change)int x,m,flag=2,flag0,i,j;string ss,part0max; flag0=flag;for(x=0;x<change.length();x+)for(m=0;m<flag0;m+)for(i=0;i<partm.length();i+)ss=move(partm.substr(i,1),changex,b);for(j=0;j<flag;j+)if(isexist(ss,partj

6、)part0j=part0j+partm.substr(i,1); if(ss="&")part0flag=part0flag+partm.substr(i,1);break;for(j=0;j<=flag;j+)if(part0j!=""&&part0j!=partm)partflag+=part0j;part0j=""partm=""else part0j=""flag0=flag;return flag;void main() int i,j,flag,x;

7、string Change;/輸入符號(hào) string ss; edge *b=new edgemax; cout<<"請(qǐng)輸入DFA各邊信息：起點(diǎn) 條件（空用&表示） 終點(diǎn)，以輸入#結(jié)束。"<<endl; for(i=0;i<max;i+) cin>>bi.first; if(bi.first="#")break; else cin>>bi.change>>bi.last; N=i; cout<<"請(qǐng)輸入該DFA的終態(tài)集合："<<endl;

8、 cin>>part1; cout<<"請(qǐng)輸入該DFA的非終態(tài)集合："<<endl; cin>>part0; cout<<"請(qǐng)輸入此DFA狀態(tài)中的輸入符號(hào)即邊上的條件:"<<endl; cin>>Change; flag=divide(b,Change); cout<<"此DFA最小化劃分的子集如下："<<endl; for(i=0;i<flag;i+) if(parti!="")cout<<

9、;parti<<endl; cout<<"用狀態(tài)A,B,C···等代替子集：" for(i=0;i<flag;i+) if(parti!="")cout<<""<<parti<<"," cout<<endl<<"則DFA最小化后的各邊信息如下："<<endl; char lettersmax; char letter='A' for(i=0;i<flag;i+) if(parti!="") lettersi=letter; +letter; for(i=0;i<flag;i+) for(j=0;j<Change.length();j+) ss=move(parti,Changej,b); if(parti!=""&&ss!="&")cout<<lettersi<<" "<&l