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

不确定有限状态自动机的确定化 【实验目的】 　输入： 非确定有限（穷）状态自动机。 输出： 确定化的有限（穷）状态自动机。 【实验原理】 　　　同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。 　　　NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。 【程序代码】 #includeiostream #includestring #includevector using namespace std; #define max 100 struct edge{ string first;//边的初始结点 string change;//边的条件 string last;//边的终点 }; int N;//NFA的边数 vectorint value; string closure(string a,edge *b) { int i,j; for(i=0;ia.length();i++) { for(j=0;jN;j++) { if(b[j].first[0]==a[i]b[j].change==) { a=a+b[j].last[0]; } } } 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(b[j].first[0]==jihe[i]b[j].change[0]==ch) s=s+b[j].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(t[j]t[k])k=j; } tt=t[k];t[k]=t[i];t[i]=tt; } return t; } void main() { int i,j,x=0,h,length,m,d=0; string Change; string First,Last;//初态，终态， string T[max],ss; edge *b=new edge[max]; cout请输入各边信息：起点 条件（空用表示） 终点，以输入#结束。endl; for(i=0;imax;i++) { cinb[i].first; if(b[i].first==#)break; else cinb[i].changeb[i].last; } N=i; cout请输入该NFA的初态及终态：endl; cinFirstLast; cout请输入此NFA状态中的输入符号即边上的条件:endl; cinChange; T[x]=closure(First,b); T[x]=sort(T[x]); value.push_back(0); i=0; while(value[i]==0value.size()) { value[i]=1; for(j=0;jChange.length();j++) { ss=; ss=move(T[i],Change[j],b); length=value.size(); for(h=0;hlength;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=new edge[max]; for(i=0;i=x;