編譯原理實(shí)驗(yàn)六：DFA最小化

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

2、面的方法進(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） 若有無關(guān)狀態(tài)，則將其刪去。根據(jù)以上方法就將確定有限自動(dòng)機(jī)進(jìn)

3、行了簡化，而且簡化后的自動(dòng)機(jī)是原自動(dòng)機(jī)的狀態(tài)最少的自動(dòng)機(jī)。四：數(shù)據(jù)結(jié)構(gòu)與算法struct edge string first;/邊的初始結(jié)點(diǎn)string condition;/邊上的條件string last;/邊的終點(diǎn);string move(string collection,char ch,edge *b)/狀態(tài)集合I的a弧轉(zhuǎn)換int divide(edge *b,string change)/分割子集法進(jìn)行DFA的最小化五：出錯(cuò)分析1：在數(shù)據(jù)結(jié)構(gòu)的定義之中，字符與字符串的差別，本次實(shí)驗(yàn)室字符串而不是字符六：實(shí)驗(yàn)結(jié)果與分析七：源代碼#include#includeusing namesp

4、ace std;#define max 100struct edge string first;/邊的初始結(jié)點(diǎn)string condition;/邊上的條件string last;/邊的終點(diǎn);int N;/NFA的邊數(shù)string partmax;/分割子集string move(string collection,char ch,edge *b)/狀態(tài)集合I的a弧轉(zhuǎn)換int i,j;string s=;for(i=0;icollection.length();i+) for(j=0;jN;j+)if(bj.first0=collectioni&bj.condition0=ch) s=s+bj

5、.last;if(s=)return &;else return s;bool isexist(string s,string d)/判斷子串是否存在在某一集合if(d!=&0=d.find(s)&d.find(s)=d.length()-1)return 1;else return 0;int divide(edge *b,string change)/分割子集法進(jìn)行DFA的最小化int x,m,flag=2,flag0,i,j;string ss,part0max; flag0=flag;for(x=0;xchange.length();x+)for(m=0;mflag0;m+)for(i

6、=0;ipartm.length();i+)ss=move(partm.substr(i,1),changex,b);for(j=0;jflag;j+)if(isexist(ss,partj)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 ma

7、in() int i,j,flag,x; string Condition;/邊上的條件 string ss; edge *b=new edgemax; cout.編譯原理實(shí)驗(yàn)六：DFA最小化.endl; cout請(qǐng)輸入DFA各邊信息：起點(diǎn) 條件（空用&表示） 終點(diǎn) 并以輸入#結(jié)束。endl; for(i=0;ibi.first; if(bi.first=#)break; else cinbi.conditionbi.last; N=i; cout請(qǐng)輸入該DFA的終態(tài)集合：part1; cout請(qǐng)輸入該DFA的非終態(tài)集合：part0; cout請(qǐng)輸入此DFA狀態(tài)中的邊上的條件:Conditio

8、n; flag=divide(b,Condition); coutDFA最小化劃分的子集如下：endl; for(i=0;iflag;i+) if(parti!=)coutpartiendl; cout用狀態(tài)A,B,C等代替子集：; for(i=0;iflag;i+) if(parti!=)coutparti,; coutendl則DFA最小化后的各邊信息如下：endl; char lettersmax; char letter=A; for(i=0;iflag;i+) if(parti!=) lettersi=letter; +letter; for(i=0;iflag;i+) for(j=0;jCondition.length();j+) ss=move(parti,Conditionj,