不確定有限狀態(tài)自動機的確定化剖析

1、不確定有限狀態(tài)自動機的確定化【實驗?zāi)康摹枯斎耄悍谴_定有限（窮）狀態(tài)自動機。輸出：確定化的有限（窮）狀態(tài)自動機。【實驗原理】同一個字符串a(chǎn)可以由多條通路產(chǎn)生，而在實際應(yīng)用中，作 為描述控制過程的自動機，通常都是確定有限自動機DFA,因此這就需要將不確定有限自動機轉(zhuǎn)換成等價的確定有限自動機，這個過程稱為不確定有限自動機的確定化，即 NFA確定化為DFA。NFA確定化的實質(zhì)是以原有狀態(tài)集上的子集作為DFA上的一個狀態(tài)，將原狀態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有限自動機確定化。經(jīng)過確定化后，狀態(tài)數(shù)可能增加，而且可能出現(xiàn)一些等 價狀態(tài)，這時就需要簡化?！境绦虼a】#in clude<iost

2、ream>#in clude<stri ng>#in clude<vector>using n amespace std;#defi ne max 100 struct edgestr ing first;/邊的初始結(jié)點stri ng cha nge;/邊的條件stri ng last;/邊的終點；int N;/NFA 的邊數(shù)vector <int> value;stri ng closure(stri ng a,edge *b)int i,j;for(i=0;i<aen gth();i+)for(j=0;j<N;j+)if(bj.firs

3、t0=ai&&bj.cha nge二二"&")a=a+bj.last0;return a; stri ng move(stri ng jihe,char ch,edge *b)int i,j;stri ng s=""for(i=0;ivjiheen gth();i+)for(j=0;j<N;j+)if(bj.first0=jihei&&bj.cha ngeO=ch) s=s+bj.last;return s; stri ng sort(stri ng t)int k,i,j;char tt;for(i=0;i

4、<t.le ngth()-1;i+)k=i;if(tj<tk)k=j;tt=tk;tk=ti;ti=tt;retur n t; void mai n()int i,j,x=O,h,le ngth,m,d=0;stri ng Chan ge;stri ng First,Last; 初態(tài)，終態(tài)，stri ng Tmax,ss;edge *b=new edgemax;coutvv"請輸入各邊信息：起點 條件(空用&表示)終點，以輸入#結(jié)束。"<<endl;for(i=0;i<max;i+)cin> >bi.first;if(bi.

5、first="#")break;elsecin> >bi.cha nge>>bi.last;N=i;coutvv"請輸入該NFA的初態(tài)及終態(tài)："<<endl;cin> >First>>Last;:"<<e ndl;coutvv"請輸入此NFA狀態(tài)中的輸入符號即邊上的條件cin> >Cha nge;Tx=closure(First,b);Tx=sort(Tx);value.push_back(O);i=0;while(valuei=0&&

6、value.size()valuei=1;for(j=0;j<Cha ngeen gth();j+)ss=move(Ti,Cha ngej,b);len gth=value.size();if(Th=sort(closure(ss,b)break;if(h=le ngth)T+x=sort(closure(ss,b);value.push_back(O); i+;edge *DFA 二new edgemax; for(i=0;iv二x;i+) 構(gòu)造 DFA 的各邊 for(j=0;j<Cha ngeen gth();j+)DFAd.first=Ti;DFAd.cha nge二Cha

7、 ngej;ss=sort(closure(move(Ti,Cha ngej,b),b);if(ss=Tm)DFAd+ast二Tm;coutvv"此NFA構(gòu)造的DFA的各邊信息如下："<<endlvv"起點 條 件終點"<<endl;for(i=0;i<d;i+)for(m=0;m<=x;m+)if(DFAi.first=Tm)cout<vmvv""<<DFAi.cha nge;for(m=0;m<=x;m+)if(DFAi.last=Tm)cout<<"

8、;"<<m<<e ndl;coutvv"該DFA的初態(tài)為："for(m=0;m<=x;m+)for(j=0;j<Tm.le ngth();j+)ss=Tm;if(ssj=First0)coutvvm<ve ndl;coutvv"該DFA的終態(tài)為："for(m=0;m<二x;m+)for(j=0;j<Tm.le ngth();j+)ss=Tm;if(ssj=Last0)cout<<mvv""cout«e ndl;system("pause");【結(jié)果截圖】溯I入各邊信息起點條件（空用氓示）甌 畑入結(jié)束0 & 10 & 31 & 21 & 42 a 3&