DFA的化简

#includestdlib.h#includestdio.h#includeiostream#includestringusingnamespacestd;#definemax100structedge{stringfirst;//边的初始结点stringchange;//边的条件stringlast;//边的终点};intN;//NFA的边数stringpart[max];//分割子集//状态集合I的a弧转换stringmove(stringjihe,charch,edge*b){inti,j;strings=;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;}}if(s==)return&;elsereturns;}//判断子串是否存在在某一集合intboolisexist(strings,stringd){if(d!=&&0=d.find(s)&&d.find(s)=d.length()-1)return1;elsereturn0;}//分割子集法进行DFA的最小化intdivide(edge*b,stringchange){intx,m,flag=2,flag0,i,j;stringss,part0[max];flag0=flag;for(x=0;xchange.length();x++){for(m=0;mflag0;m++){for(i=0;ipart[m].length();i++){ss=move(part[m].substr(i,1),change[x],b);for(j=0;jflag;j++){if(boolisexist(ss,part[j]))part0[j]=part0[j]+part[m].substr(i,1);if(ss==&){part0[flag]=part0[flag]+part[m].substr(i,1);break;}}}for(j=0;j=flag;j++){if(part0[j]!=&&part0[j]!=part[m]){part[flag++]=part0[j];part0[j]=;part[m]=;}elsepart0[j]=;}}flag0=flag;}returnflag;}intmain(){inti,j,flag,x;stringChange;//输入符号stringss;edge*b=newedge[max];printf(请输入DFA各边信息：起点条件（空用&表示）终点，以输入#结束。);for(i=0;imax;i++){cinb[i].first;if(b[i].first==#)break;elsecinb[i].changeb[i].last;}N=i;printf(请输入该DFA的终态集合：);cinpart[1];printf(请输入该DFA的非终态集合：);cinpart[0];printf(请输入此DFA状态中的输入符号即边上的条件:);cinChange;flag=divide(b,Change);printf(此DFA最小化划分的子集如下：);for(i=0;iflag;i++){if(part[i]!=)coutpart[i]endl;}printf(用状态A,B,C···等代替子集：);for(i=0;iflag;i++){if(part[i]!=)cout{part[i]},;}printf(则DFA最小化后的各边信息如下：\n);charletters[max];charletter='A';for(i=0;iflag;i++){if(part[i]!=){letters[i]=letter;++letter;}}for(i=0;iflag;i++)for(j=0;jChange.length();j++){ss=move(part[i],Change[j],b);if(part[i]!=&&ss!=&)coutletters[i]Change[j];for(x=0;xflag;x++)if(boolisexist(ss.substr(0,1),part[x]))coutletters[x]endl;}system(pause);return0;}