編譯原理實驗報告實驗名稱不確定有限狀態自動機的確定化實驗時間院系計算機科學與技術學院班級學號姓名試驗目的輸入：非確定有限(窮)狀態自動機。輸出：確定化的有限(窮)狀態自動機實驗原理一個確定的有限自動機(DFA)M可以定義為一個五元組，M=(K,￡,F,S,Z),其中：K是一個有窮非空集，集合中的每個元素稱為一個狀態；E是一個有窮字母表，E中的每個元素稱為一個輸入符號；F是一個從KX￡fK的單值轉換函數，即F(R,a)=Q,(R,QGK)表示當前狀態為R,如果輸入字符a,則轉到狀態Q,狀態Q稱為狀態R的后繼狀態；SGK，是惟一的初態；ZWK,是一個終態集。由定義可見，確定有限自動機只有惟一的一個初態，但可以有多個終態，每個狀態對字母表中的任一輸入符號，最多只有一個后繼狀態。對于DFAM,若存在一條從某個初態結點到某一個終態結點的通路，則稱這條通路上的所有弧的標記符連接形成的字符串可為DFAM所接受。若M的初態結點同時又是終態結點，則稱e可為M所接受(或識別)，DFAM所能接受的全部字符串(字)組成的集合記作L(M)。一個不確定有限自動機(NFA)M可以定義為一個五元組，M=(K，￡，F,S,Z),其中：k是一個有窮非空集，集合中的每個元素稱為一個狀態；￡是一個有窮字母表，￡中的每個元素稱為一個輸入符號；F是一個從KX￡fK的子集的轉換函數；SWK,是一個非空的初態集；ZWK，是一個終態集。由定義可見，不確定有限自動機NFA與確定有限自動機DFA的主要區別是：由以上定義可知，若兩個自動機能夠接受相同的語言，則稱這兩個自動機等價。DFA是NFA的特例，因此對于每一個NFAM總存在一個DFAM，使得L(M)=L(M)。即一個不確定有限自動機能接受的語言總可以找到一個舍價的確定看一2一一―一限自動機來接受該語言。NFA確定化為DFA同一個字符串a可以由多條通路產生，而在實際應用中，作為描述控制過程的自動機，通常都是確定有限自動機DFA，因此這就需要將不確定有限自動機轉換成等價的確定有限自動機，這個過程稱為不確定有限自動機的確定化，即NFA確定化為DFA。下面介紹一種NFA的確定化算法，這種算法稱為子集法：若NFA的全部初態為S1，S2，…，S，則令DFA的初態為：sff…，sj其中方括號用來表示若干個狀態構成的某一狀態。設DFA的狀態集K中有一狀態為［S.，S.+1，…，S.］，若對某符號aeL，在NFA中有F({S.，S.+1，…，句}，a)={S；，S."…，Sj}則令F({S.，S.+1，…，S.}，a)={S.’，S」，…，Sk’}^DFA的一個轉換函數。若［S,S：，…，Sk‘］不在K中，則將其作為新的狀態加入到3中。重復第2步，直到K中不再有新的狀態加入為止。上面得到的所有狀態構成DFA的狀態集K，轉換函數構成DFA的F，DFA的字母表仍然是NFA的字母表L。DFA中凡是含有NFA終態的狀態都是DFA的終態。對于上述NFA確定化算法一^集法，還可以采用另一種操作性更強的描述方式，下面我們給出其詳細描述。首先給出兩個相關定義。假設1是NFAM狀態集K的一個子集(即ieK)，則定義e-closure(I)為：若Qei，則Qee-closure(I)；若Qei，則從Q出發經過任意條e弧而能到達的任何狀態Q'，^UQ’ee-closure(I)。狀態集e-closure(I)稱為狀態I的e閉包。假設NFAM=(K，L，F，S，Z)，若IeK，aeL，則定義I=e-closure(J)，其中J是所有從e-closure(I)出發，經過一條a弧而到達的狀態集。NFA確定化的實質是以原有狀態集上的子集作為DFA上的一個狀態，將原狀態間的轉換為該子集間的轉換，從而把不確定有限自動機確定化。經過確定化后，狀態數可能增加，而且可能出現一些等價狀態，這時就需要簡化。3..實驗內容輸入：非確定有限(窮)狀態自動機。輸出：確定化的有限(窮)狀態自動機4.實驗心得5.實驗代碼與結果#include<iostream>#include<string>#include<vector>usingnamespacestd;#definemax100structedge(stringfirst;//邊的初始結點stringchange;//邊的條件stringlast;//邊的終點};intN;//NFA的邊數vector<int>value;stringclosure(stringa,edge*b)(inti,j;for(i=0;i<a.length();i++)(for(j=0;j<N;j++)(if(b[j].first[0]==a[i]&&b[j].change=="&")a=a+b[j].last[0];}}}returna;}stringmove(stringjihe,charch,edge*b)(inti,j;strings="";for(i=0;i<jihe.length();i++)(for(j=0;j<N;j++)(if(b[j].first[0]==jihe[i]&&b[j].change[0]==ch)s=s+b[j].last;}}returns;}stringsort(stringt)intk,i,j;chartt;for(i=0;i<t.length()-1;i++)(k=i;for(j=i+1;j<t.length();j++)(if(t[j]<t[k])k=j;}tt=t[k];t[k]=t[i];t[i]=tt;}returnt;}voidmain()(inti,j,x=0,h,length,m,d=0;stringChange;stringFirst,Last;//初態，終態，stringT[max],ss;edge*b=newedge[max];cout<<"請輸入各邊信息：起點條件(空用&表示)終點，以輸入#結束。"<<endl;for(i=0;i<max;i++)(cin>>b[i].first;if(b[i].first=="#")break;elsecin>>b[i].change>>b[i].last;}N=i;cout<<"請輸入該NFA的初態及終態："<<endl;cin>>First>>Last;cout<<"請輸入此NFA狀態中的輸入符號即邊上的條件:"<<endl;cin>>Change;T[x]=closure(First,b);T[x]=sort(T[x]);value.push_back(0);i=0;while(value[i]==0&&value.size())value[i]=1;for(j=0;j<Change.length();j++)(ss="";ss=move(T[i],Change[j],b);length=value.size();for(h=0;h<length;h++)(if(T[h]==sort(closure(ss,b)))break;}if(h==length)(T[++x]=sort(closure(ss,b));value.push_back(0);}}i++;}edge*DFA=newedge[max];for(i=0;i<=x;i++)//構造DFA的各邊for(j=0;j<Change.length();j++)(DFA[d].first=T[i];DFA[d].change=Change[j];ss="";ss=sort(closure(move(T[i],Change[j],b),b));for(m=0;m<=x;m++)if(ss==T[m])DFA[d++].last=T[m];}}cout<<"此NFA構造的DFA的各邊信息如下："<<endl<<"起點條件終點"<<endl;for(i=0;i<d;i++)(for(m=0;m<=x;m++)(if(DFA[i].first==T[m])cout<<m<<""<<DFA[i].change;}for(m=0;m<=x;m++)if(DFA[i].last==T[m])cout<<""<<m<<endl;;}cout<<"該DFA的初態為：”for(m=0;m<=x;m++)(for(j=0;j<T[m].length();j++)(ss=T[m];if(ss[j]==First[0])cout<<m<<endl;}}cout<<"該DFA的終態為："；for(m=0;m<=x;m++)(for(j=0;j<T[m].length();j++)(ss=T[m];if(ss[j]==Last[0])cout<<m<<"";}}cout<<endl;system("pause");(1)NFA的初始狀態S為一個狀態集，即允許有多個初始狀態；(2)NFA中允許狀態在某輸出邊上有相同的符號，即對同一個輸入符號可以有多個后繼狀態。即DFA中的F是單值函數，而NFA中的F是多值函數。因此，可以將確定有限自動機DFA看作是不確定有限自動機NFA的特例。和DFA—樣，NFA也