編譯原理實驗六：DFA最小化(共7頁)

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

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

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

4、#include<iostream>#include<string>using namespace std;#define max 100struct edge string first;/邊的初始結(jié)點string condition;/邊上的條件string last;/邊的終點;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;i<collection.len

5、gth();i+) for(j=0;j<N;j+)if(bj.first0=collectioni&&bj.condition0=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.length()-1)return 1;else return 0;int

6、divide(edge *b,string change)/分割子集法進行DFA的最小化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)part0j=part0j+partm.substr(i,1); if(s

7、s="&")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; string Condition;/邊上的條件 string ss; edg

8、e *b=new edgemax; cout<<".編譯原理實驗六：DFA最小化."<<endl; cout<<"請輸入DFA各邊信息：起點 條件（空用&表示） 終點 并以輸入#結(jié)束。"<<endl; for(i=0;i<max;i+) cin>>bi.first; if(bi.first="#")break; else cin>>bi.condition>>bi.last; N=i; cout<<"請輸入該DFA的

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

10、"")cout<<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<Condition.length();j+) ss=move(parti,Conditionj,b); if(parti!=""&&ss!="&")cout<<lettersi<<&quo