您好,欢迎访问三七文档
编译原理实验报告实验名称DFA的最小化实验时间院系班级学号姓名1.试验目的掌握DFA的最小化2.实验原理所谓自动机的化简问题即是对任何一个确定有限自动机DFAM,构造另一个确定有限自动机DFAM’,有L(M)=L(M’),并且M’的状态个数不多于M的状态个数,而且可以肯定地说,能够找到一个状态个数为最小的M’。下面首先来介绍一些相关的基本概念。设Si是自动机M的一个状态,从Si出发能导出的所有符号串集合记为L(Si)。设有两个状态Si和Sj,若有L(Si)=L(Sj),则称Si和Sj是等价状态。下图所示的自动机中L(B)=L(C)={1},所有状态B和状态C是等价状态。又例如终态导出的符号串集合中必然包含空串ε,而非终止状态导出的符号串集合中不可能包含空串ε,所以终态和非终止状态是不等价的。对于等价的概念,我们还可以从另一个角度来给出定义。给定一个DFAM,如果从某个状态P开始,以字符串w作为输入,DFAM将结束于终态,而从另一状态Q开始,以字符串w作为输入,DFAM将结束于非终止状态,则称字符串w把状态P和状态Q区分开来。把不可区分开来的两个状态称为等价状态。设Si是自动机M的一个状态,如果从开始状态不可能达到该状态Si,则称Si为无用状态。设Si是自动机M的一个状态,如果对任何输入符号a都转到其本身,而不可能达到终止状态,则称Si为死状态。化简DFA关键在于把它的状态集分成一些两两互不相交的子集,使得任何两个不相交的子集间的状态都是可区分的,而同一个子集中的任何两个状态都是等价的,这样可以以一个状态作为代表而删去其他等价的状态,然后将无关状态删去,也就获得了状态数最小的DFA。下面具体介绍DFA的化简算法:(1)首先将DFAM的状态划分出终止状态集K1和非终止状态集K2。K=K1∪K2由上述定义知,K1和K2是不等价的。(2)对各状态集每次按下面的方法进一步划分,直到不再产生新的划分。设第i次划分已将状态集划分为k组,即:K=K1(i)∪K2(i)∪…∪Kk(i)1ABCD011对于状态集Kj(i)(j=1,2,…,k)中的各个状态逐个检查,设有两个状态Kj’、Kj’’∈Kj(i),且对于输入符号a,有:F(Kj',a)=KmF(Kj'',a)=Kn如果Km和Kn属于同一个状态集合,则将Kj’和Kj’’放到同一集合中,否则将Kj’和Kj’’分为两个集合。(3)重复第(2)步,直到每一个集合不能再划分为止,此时每个状态集合中的状态均是等价的。(4)合并等价状态,即在等价状态集中取任意一个状态作为代表,删去其他一切等价状态。(5)若有无关状态,则将其删去。根据以上方法就将确定有限自动机进行了简化,而且简化后的自动机是原自动机的状态最少的自动机。3..实验内容输入:DFA。输出:最小化的DFA。3.实验心得通过这次实验,加深了对DFA最小化的方法的理解,学会了实现DFA最小化的方法,化简DFA关键在于把它的状态集分成一些两两互不相交的子集,使得任何两个不相交的子集间的状态都是可区分的,而同一个子集中的任何两个状态都是等价的,这样可以以一个状态作为代表而删去其他等价的状态,然后将无关状态删去,也就获得了状态数最小的DFA。4.实验代码与结果#includeiostream#includestring#includealgorithmusingnamespacestd;intN,M=2;intt=0,x=0,c=0,d=0,z=0,h=0;;stringstate[5];#definemaxs100structedge{stringprim;stringchan;stringres;};structjihe{stringgroup1;stringgroup2;stringgroup3;intflag1;intflag2;};stringshan(string&s){strings1;for(inti=0;is.length();i++){intflag=0;for(intj=i+1;js.length();j++)if(s[i]==s[j])flag=1;if(flag==0)s1+=s[i];}returns1;}voidinput(edge*p,jihe*g){inti;cinN;cout产生式个数:Nendl;for(i=0;iM;i++)cinstate[i];cout输入为:;for(i=0;iM;i++)coutstate[i];coutendl;for(i=0;iN;i++)cinp[i].primp[i].chanp[i].res;cing[t].group1;cing[++t].group1;cout产生式为:endl;for(i=0;iN;i++)coutp[i].primp[i].chanp[i].resendl;}stringjian(strings1,strings2){strings3;intflag;for(inti=0;is1.length();i++){flag=0;for(intj=0;js2.length();j++){if(s1[i]==s2[j])flag++;}if(flag==0)s3+=s1[i];}returns3;}voidDivide(strings1,edge*p,jihe*g){inti,j,k,l,v=-1,r=-1,flag=0,flag1,b;strings,s2,s3;s=s1;for(k=0;ks.length();k++){for(i=0;iN;i++)if(s[k]==p[i].prim[0]){flag1=0;for(j=0;jN;j++)if(i!=j&&s[k]==p[j].prim[0]){flag1++;break;}if(flag10){if(p[i].chan==state[0]&&p[j].chan==state[1]){for(l=c;l=t;l++)for(intq=0;qg[l].group1.length();q++)if(p[i].res[0]==g[l].group1[q])g[k].flag1=l;for(l=c;l=t;l++)for(intq=0;qg[l].group1.length();q++)if(p[j].res[0]==g[l].group1[q])g[k].flag2=l;}}else{if(p[i].chan==state[0]||p[i].chan==state[0])for(l=c;l=t;l++)for(intq=0;qg[l].group1.length();q++)if(p[i].res[0]==g[l].group1[q])g[k].flag1=l;for(l=c;l=t;l++)for(intq=0;qg[l].group1.length();q++)if(p[j].res[0]==g[l].group1[q])g[k].flag2=l;}}}for(i=0;is.length();i++)for(j=0;js.length();j++)if(i!=j)if(g[i].flag1==g[j].flag1&&g[i].flag2==g[j].flag2){if(r==-1&&v==-1){s2+=s[i];s2+=s[j];flag++;r=g[i].flag1;v=g[i].flag2;}else{if(r==g[i].flag1&&v==g[i].flag2){s2+=s[i];s2+=s[j];flag++;r=g[i].flag1;v=g[i].flag2;}}}sort(s2.begin(),s2.end());s2=shan(s2);if(flag0){if(s2!=s){g[++t].group1=s2;b=t;g[++t].group1=jian(g[d].group1,g[b].group1);c++;}else{g[++t].group1=s2;c++;}}else{for(i=0;is.length();i++){g[++t].group1=s[i];}c++;}}intmain(){freopen(intext.txt,r,stdin);inti,b,j;stringss;edge*p=newedge[maxs];edge*y=newedge[maxs];jihe*g=newjihe[maxs];input(p,g);while(d=t){if(t50)//根据情况取值,使之不能再划分Divide(g[d].group1,p,g);d++;}//for(i=0;it;i++)//coutg[i].group1endl;for(i=c;i=t;i++)g[x++].group2=g[i].group1;cout********************************endl;cout划分子集为:endl;for(i=0;ix;i++)g[i].group3='A'+i;for(i=0;ix;i++)coutg[i].group2\tg[i].group3endl;for(i=0;iN;i++)for(j=0;jx;j++)for(b=0;bg[j].group2.length();b++){if(p[i].prim[0]==g[j].group2[b])p[i].prim=g[j].group3;if(p[i].res[0]==g[j].group2[b])p[i].res=g[j].group3;}cout**************************************endl;cout重命名为:endl;for(i=0;iN;i++)coutp[i].prim\tp[i].chan\tp[i].resendl;cout********************************endl;cout最小化为:endl;for(i=0;iN;i++)for(j=0;jN;j++)if(i!=j)if(p[i].prim==p[j].prim&&p[i].chan==p[j].chan&&p[i].res==p[j].res){p[j].prim=\0;p[j].chan=\0;p[j].res=\0;}for(i=0;iN;i++)if(p[i].prim[0]){y[z].prim=p[i].prim;y[z].chan=p[i].chan;y[z].res=p[i].res;z++;}//for(i=0;iz;i++)//couty[i].primy[i].chany[i].resendl;for(i=0;iz;i++)ss+=y[i].prim[0];ss=shan(ss);coutstate[0]state[1]endl;for(j=0;jss.length();j++){coutss[j];for(i=0;iz;i++)if(ss[j]==y[i].prim[0])couty[i].res;coutendl;}return0;}
本文标题:DFA最小化
链接地址:https://www.777doc.com/doc-5225050 .html