編譯原理實驗五有窮自動機的確定化

1、實驗五：有窮自動機的確定化一：要求1.輸入： 非確定有限（窮）狀態(tài)自動機。2.輸出： 確定化的有限（窮）狀態(tài)自動二：實驗目的1. 熟練掌握DFA及NFA的定義及有關概念。2. 理解并掌握確定的有窮自動機的化簡等算法。三：實驗原理1.由定義可見，不確定有限自動機NFA與確定有限自動機DFA的主要區(qū)別是：（1）NFA的初始狀態(tài)S為一個狀態(tài)集，即允許有多個初始狀態(tài)；（2）NFA中允許狀態(tài)在某輸出邊上有相同的符號，即對同一個輸入符號可以有多個后繼狀態(tài)。即DFA中的F是單值函數，而NFA中的F是多值函數。2. NFA確定化為DFA同一個字符串可以由多條通路產生，而在實際應用中，作為描述控制過程的自動機，

2、通常都是確定有限自動機DFA，因此這就需要將不確定有限自動機轉換成等價的確定有限自動機，這個過程稱為不確定有限自動機的確定化，即NFA確定化為DFA。下面介紹一種NFA的確定化算法，這種算法稱為子集法：（1）若NFA的全部初態(tài)為S1，S2，Sn，則令DFA的初態(tài)為：SS1，S2，Sn，其中方括號用來表示若干個狀態(tài)構成的某一狀態(tài)。（2）設DFA的狀態(tài)集K中有一狀態(tài)為Si，Si+1，Sj，若對某符號a，在NFA中有F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 則令F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 為DFA的一個轉換函數。若 Si，Si+1，Sk 不在K中，則

3、將其作為新的狀態(tài)加入到K中。（3）重復第2步，直到K中不再有新的狀態(tài)加入為止。（4）上面得到的所有狀態(tài)構成DFA的狀態(tài)集K，轉換函數構成DFA的F，DFA的字母表仍然是NFA的字母表。（5）DFA中凡是含有NFA終態(tài)的狀態(tài)都是DFA的終態(tài)。3. NFA確定化的實質是以原有狀態(tài)集上的子集作為DFA上的一個狀態(tài)，將原狀態(tài)間的轉換為該子集間的轉換，從而把不確定有限自動機確定化。經過確定化后，狀態(tài)數可能增加，而且可能出現一些等價狀態(tài)，這時就需要簡化。四：數據結構與算法struct edge string first;/邊的初始結點string condition;/邊上的條件string last;/

4、邊的終點;string closure(string a,edge *b)/求狀態(tài)集合I的&-閉包，用&代替"空"string move(string collection,char ch,edge *b)/狀態(tài)集合I的a弧轉換string sort(string t)/字符串排序五：出錯分析1:缺少#include<vector>，會有很多錯誤。2:在數據結構的定義之中，字符與字符串的差別，本次實驗室字符串而不是字符六：實驗結果與分析七：源代碼#include<iostream>#include<string>#incl

5、ude<vector>using namespace std;#define max 100int n;/NFA的邊數vector<int> value;struct edge string first;/邊的初始結點string condition;/邊上的條件string last;/邊的終點;string closure(string a,edge *b)/求狀態(tài)集合I的&-閉包，用&代替"空"int i,j;for(i=0;i<a.length();i+)for(j=0;j<n;j+)if(bj.first0=ai

6、&&bj.condition="&")a=a+bj.last0;return a;string move(string collection,char ch,edge *b)/狀態(tài)集合I的a弧轉換int i,j;string s=""for(i=0;i<collection.length();i+) for(j=0;j<n;j+)if(bj.first0=collectioni&&bj.condition0=ch) s=s+bj.last;return s;string sort(string t)/字

7、符串排序int k,i,j;char tt;for(i=0;i<t.length()-1;i+)k=i;for(j=i+1;j<t.length();j+)if(tj<tk)k=j;tt=tk;tk=ti;ti=tt;return t;void main() int i,j,x=0,h,length,m,d=0; string Condition;/邊上的條件 string First,Last;/初態(tài)，終態(tài)， string Tmax,ss; edge *b=new edgemax; cout<<".編譯原理實驗五：有窮自動機的確定化."<

8、;<endl; cout<<"請輸入各邊信息：起點 條件（空用&表示） 終點 并以輸入#結束！"<<endl; for(i=0;i<max;i+)/存儲每條邊信息 cin>>bi.first; if(bi.first="#")break; else cin>>bi.condition>>bi.last; n=i; cout<<"請輸入NFA的初態(tài)及終態(tài)："<<endl; cin>>First>>Last; c

9、out<<"請輸入NFA狀態(tài)中的輸入符號即邊上的條件:"<<endl; cin>>Condition; Tx=closure(First,b);/字符串數組存儲空閉包并排序 Tx=sort(Tx); value.push_back(0); i=0; while(valuei=0&&value.size() valuei=1; for(j=0;j<Condition.length();j+) ss="" ss=move(Ti,Conditionj,b); length=value.size(); f

10、or(h=0;h<length;h+) if(Th=sort(closure(ss,b)break; if(h=length) T+x=sort(closure(ss,b); value.push_back(0); i+; edge *DFA=new edgemax; for(i=0;i<=x;i+)/構造DFA的各邊 for(j=0;j<Condition.length();j+) DFAd.first=Ti; DFAd.condition=Conditionj; ss="" ss=sort(closure(move(Ti,Conditionj,b),b

11、); for(m=0;m<=x;m+) if(ss=Tm)DFAd+.last=Tm; cout<<"NFA構造的DFA的各邊信息如下："<<endl<<"起點 條件 終點"<<endl; for(i=0;i<d;i+) for(m=0;m<=x;m+) if(DFAi.first=Tm)cout<<m<<" "<<DFAi.condition; for(m=0;m<=x;m+) if(DFAi.last=Tm)cout<<" "<<m<<endl; cout<<"確定后的DFA的初態(tài)為：" for(m=0;m<=x;m+) for(j=0;j<Tm.length();j+) ss=Tm; if(ssj=First0)cout<<m<<endl; cou