不确定有限状态自动机的确定化.doc

不确定有限状态自动机的确定化【实验目的】输入： 非确定有限（穷）状态自动机。 输出： 确定化的有限（穷）状态自动机。【实验原理】同一个字符串可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。【程序代码】#include#include#includeusing namespace std;#define max 100struct edge string first;/边的初始结点string change;/边的条件string last;/边的终点;int N;/NFA的边数vector value;string closure(string a,edge *b)int i,j;for(i=0;ia.length();i+)for(j=0;jN;j+)if(bj.first0=ai&bj.change=&)a=a+bj.last0;return a;string move(string jihe,char ch,edge *b)int i,j;string s=;for(i=0;ijihe.length();i+) for(j=0;jN;j+)if(bj.first0=jihei&bj.change0=ch) s=s+bj.last;return s;string sort(string t)int k,i,j;char tt;for(i=0;it.length()-1;i+)k=i;for(j=i+1;jt.length();j+)if(tjtk)k=j;tt=tk;tk=ti;ti=tt;return t;void main() int i,j,x=0,h,length,m,d=0; string Change; string First,Last;/初态，终态， string Tmax,ss; edge *b=new edgemax; cout请输入各边信息：起点 条件（空用&表示） 终点，以输入#结束。endl; for(i=0;ibi.first; if(bi.first=#)break; else cinbi.changebi.last; N=i; cout请输入该NFA的初态及终态：FirstLast; cout请输入此NFA状态中的输入符号即边上的条件:Change; Tx=closure(First,b); Tx=sort(Tx); value.push_back(0); i=0; while(valuei=0&value.size() valuei=1; for(j=0;jChange.length();j+) ss=; ss=move(Ti,Changej,b); length=value.size(); for(h=0;hlength;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;jChange.length();j+) DFAd.first=Ti; DFAd.change=Changej; ss=; ss=sort(closure(move(Ti,Changej,b),b); for(m=0;m=x;m+) if(ss=Tm)DFAd+.last=Tm; cout此NFA构造的DFA的各边信息如下：endl起点 条件 终点endl; for(i=0;id;i+) for(m=0;m=x;m+) if(DFAi.first=Tm)coutm DFAi.change; for(m=0;m=x;m+) if(DFAi.last=Tm)cout mendl; cout该DFA的初态为：; for(m=0;m=x;m+) for(j=0;jTm.length();j+) ss=Tm; if(ssj=First0)coutmendl; cout该DFA的终态为：; f