不确定有限状态自动机的确定化剖析

1、不确定有限状态自动机的确定化【实验目的】输入：非确定有限（穷）状态自动机。输出：确定化的有限（穷）状态自动机。【实验原理】同一个字符串a可以由多条通路产生，而在实际应用中，作 为描述控制过程的自动机，通常都是确定有限自动机DFA,因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即 NFA确定化为DFA。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等 价状态，这时就需要简化。【程序代码】#in clude<iost

2、ream>#in clude<stri ng>#in clude<vector>using n amespace std;#defi ne max 100 struct edgestr ing first;/边的初始结点stri ng cha nge;/边的条件stri ng last;/边的终点；int N;/NFA 的边数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; 初态，终态，stri ng Tmax,ss;edge *b=new edgemax;coutvv"请输入各边信息：起点 条件(空用&表示)终点，以输入#结束。"<<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的初态及终态："<<endl;cin> >First>>Last;:"<<e ndl;coutvv"请输入此NFA状态中的输入符号即边上的条件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+) 构造 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构造的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的初态为："for(m=0;m<=x;m+)for(j=0;j<Tm.le ngth();j+)ss=Tm;if(ssj=First0)coutvvm<ve ndl;coutvv"该DFA的终态为："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");【结果截图】溯I入各边信息起点条件（空用氓示）瓯 畑入结束0 & 10 & 31 & 21 & 42 a 3&