《实验五DFA的最小化》由会员分享，可在线阅读，更多相关《实验五DFA的最小化（6页珍藏版）》请在金锄头文库上搜索。
1、编译原理实验报告实验五：DFA的最小化实验目的：1. 熟练掌握DFA及NFA的定义及有关概念。2. 理解并掌握确定的有穷自动机的最小化等算法。实验要求：输入：DFAo输出：最小化的DFAo实验原理：1化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去,也就获得了状态数最小的DFAC2.DFA的化简算法：（1）首先将DFAM的状态划分出终止状态集Ki和非终止状态集K2oK=KiUK2由上述定义知，和是不等价的。（2）对各状态集每次按下面的
2、方法进一步划分，直到不再产生新的划分。设第i次划分己将状态集划分为k组，BP：K=K）UK2（i）U.UKk对于状态集Kj（i）（j=l/2/.,k）中的各个状态逐个检查，设有两个状态KjKj丘即）,且对于输入符号a,有：F（K；,a）=KmF（Kj,a）=Kn如果Km和Kn属于同一个状态集合，则将Kf和Kj放到同一集合中，否则将Kf和Kj分为两个集合。（3）重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。（4）合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。（5）若有无关状态，则将其删去。根据以上方法就将确定有限自动机进行了简化，
3、而且简化后的自动机是原自动机的状态最少的自动机。实验内容:程序代码如下：#include#includeusingnamespacestd;#definemax100structedgestringfirst;/边的初始结点stringchange;/边的条件stringlast;/边的终点；intN;/NFA的边数stringpartfmax;/分割子集状态集合I的a弧转换stringmove(stringjihe,charch,edge*b)inti,j;strings=;for(i=0;ijihe.length();i+)for(j=0;jN;j+)if(bj.firstO=jihei&
4、bj.change0=ch)s=s+bjast;if(s=,u)return&“；elsereturns;判断子串是否存在在某一集合boolisexist(strings,stringd)if(d!=,M&0=d.find(s)&d.find(s)=d.length()-l)return1;elsereturn0;分割子集法进行DFA的最小化intdivide(edge*b,stringchange)intx,m/flag=2/flagOJ/j;stringss,partOmax;flagO=flag;for(x=0;xchangeength();x+)for(m=0;mflag0;m+)fo
5、r(i=0;ipartm.length();i+)ss=move(partm.substr(i,l)/changex,b);for(j=0;jflag;j+)if(isexist(ss/partj)partOj=partOj+partm.substr(i/l)；if(ss=&)partOflag=partOflag+partm.substr(i/l);break;for(j=0;j=flag;j+)if(partOj!=,H&partO0!=partm)partflag+=partOj;partO0=，m；partm=,;elsepartOj=,M;flagO=flag;returnflag;
6、voidmain()intijflag,x;stringChange;/输入符号stringss;edge*b=newedgemax;cout请输入DFA各边信息：起点条件(空用&表示)终点，以输入#结束。endl;for(i=0;ibifirst;if(bi.first=,#,l)break;elsecinbi.changebi.last;N=i;cout请输入该DFA的终态集合：endl;cinpartl;cout请输入该DFA的非终态集合：“partO;cout请输入此DFA状态中的输入符号即边上的条件:“Change;flag=divide(b,Change);coutH此DFA最小化
7、划分的子集如下：“vvendl;for(i=0;iflag;i+)if(parti!=,)coutpartiendl;cout用状态A,B,C等代替子集：；for(i=0;iflag;i+)if(parti!=ll,)coutl,llparti,/,1;coutendl则DFA最小化后的各边信息如T：Mendl;charlettersmax;charletter=,A,;for(i=0;iflag;i+)if(parti!=m,)lettersi=letter;+letter;for(i=0;iflag;i+)for(j=0;jChange.length();j+)ss=move(parti,
8、Changej,b);if(parti!=,n&ss曰&)coutlettersi“,ChangeUufor(x=0;xflag;x+)if(isexist(ss.substr(0,l)zpartx)coutlettersxendl;system(,pause)；实验运行结果如下：a77a47b2aaa44566傩DEAABEc意IMbabababftBccDDEE请5467341请输入该DFR的终态集合：56?请输入该DFA的非终态集合；1234请输人此DFA状态中的输入符号即边上的条件：a.b此DPA最小化划分的子集如下:1256734用状态A.B.C等代替子集,则DFA最小花后的各谢言息如下:AaCAbDinBaC
