不确定有穷自动机的确定化.docxVIP

编译原理实验报告实验名称不确定有穷自动机的确定化实验时间_____ 2014年4月10日_______院系_______管理信息工程学院_______班级_______11计算机科学与技术____学号______201101020109____________姓名________姜高__________________实验目的不确定有穷自动机的确定化实验原理用子集构造算法构造子集加入子集族中直到收敛（所有构造的子集都已存在于子集族）为止。如原来不确定有穷自动机的五元组形式为：M=（K，，F，S，Z），其中K为状态集，为字母表，F为转换函数，S为初始态，Z为终态集。用子集族S代替K，新的转换函数D代替F，形成新的五元组M=（S，，D，S，Z）即将原不确定有穷自动机转换为确定有穷自动机。实验内容闭包计算：closure(I)转换函数：move(I,a)伪代码假定构造的子集族为S=（T1，T2。。。。。。）， K为状态集：开始，令closure(K0)为S中唯一成员，并且未被标记WHILE（C中存在尚未被标记的子集T）DO{标记T;For 每输入字母a DO{U:=closure(move(T,a));If U 不在S中 then将U作为未被标记的子集加在S中}}5.代码实现#includeiostream #includestring #define MAXS 100 using namespace std; string NODE; //结点集合string CHANGE; //终结符集合int N; //NFA边数struct edge{ string first; string change; string last; }; structchan{ stringltab; stringjihe[MAXS]; }; voidkong(int a) { inti; for(i=0;ia;i++) cout ; } //排序voidpaixu(string a) { inti,j; char b; for(j=0;ja.length();j++) for(i=0;ia.length();i++) if(NODE.find(a[i])NODE.find(a[i+1])) { b=a[i]; a[i]=a[i+1]; a[i+1]=b; } }voideclouse(char c,string he,edge b[]) { int k; for(k=0;kN;k++) { if(c==b[k].first[0]) if(b[k].change==*) { if(he.find(b[k].last)he.length()) he+=b[k].last; eclouse(b[k].last[0],he,b); } } } void move(chan he,intm,edge b[]) { inti,j,k,l; k=he.ltab.length(); l=he.jihe[m].length(); for(i=0;ik;i++) for(j=0;jN;j++) if((CHANGE[m]==b[j].change[0])(he.ltab[i]==b[j].first[0])) if(he.jihe[m].find(b[j].last[0])he.jihe[m].length()) he.jihe[m]+=b[j].last[0]; for(i=0;il;i++) for(j=0;jN;j++) if((CHANGE[m]==b[j].change[0])(he.jihe[m][i]==b[j].first[0])) if(he.jihe[m].find(b[j].last[0])he.jihe[m].length()) he.jihe[m]+=b[j].last[0]; } //输出voidoutputfa(intlen,inth,chan *t) { inti,j,m; cout I ; for(i=0;ilen;i++) coutICHANGE[i] ; coutendl-------------------------endl; for(i=0;ih;i++) { cout t[i].ltab; m=t[i].ltab.length(); for(j=0;jlen;j++) { kong(8-m); m=t[i].jihe[j].length(); coutt[i].jihe[j]; } coutendl; } } void main() { edge *b=new edge[MAXS]; inti,j,k,m,n,h,x,y,len; bool flag; stringj