编译原理实验六dfa最小化

《编译原理实验六dfa最小化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验六：DFA最小化要求输入：DFA。输出：敁小化的DFA。二：实验目的1.熟练掌握DFA及NFA的定义及奋关概念。2.理解并掌握确定的冇穷自动机的敁小化等算法。三：实验原理1.化简DFA关键在于把它的状态集分成一些两两互不和交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集屮的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去，也就获得了状态数最小的DFA。2.DFA的化简算法：(1)首先将DFAM的状态划分岀终止状态集K和非终止状态集K2。K=KiUK2由上述定义知，心和1<2是不等价的。(2)对各状态

2、集每次按下面的方法进一步划分，直到不再产生新的划分。设第i次划分已将状态集划分为k组，即：K=K,(i)UK2(i)U...UKk(i)对于状态集Kj(i)(j=l，2，...，k)屮的各个状态逐个检查，设有两个状态Kf、KfeKj(i),11对于输入符号a,冇：F(Kf，a)=KmF(Kj”，a)=Kn如果K„jnKn属于同一个状态集合，则将Kj’和K/’放到同一集合中，否则将Kj’和Kf分为两个集合。(3)重复第(2)步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。(4)合并等价状态，即在等价状态集屮取任意一个状态作为代表，删去其他一切等

3、价状态。(5)若有无关状态，则将其删去。根据以上方法就将确定冇限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的Cl动机。:据结构与算法structedge{stringfirst;//边的初始结点stringcondition;//边上的条件stringlast;//边的终点}；stringmove(stringcollection,charch,edge純)//状态集合I的a弧转换intdivide(edge*b,stringchange)//分割子集法进行DFA的最小化五：出错分析1:在数据结构的定义之中，字符与字符串的差别，本次实验室字符中而不是

4、字符cj『S六：实验结果与分析■E:stiA计算机编译原涅实验实验566Debug6.exe.a6b3a7b3a1a4b6a7b3a4b1a4b2请输入该DFA的终态集合：567请输入该DFA的非终态集合：1234请输入此DFA状态中的边上的条件:^最小化划分的子集如下：用状态A.B.C•••等代替子集：<12>.<5>,<67>.<3>.<4>,脚JDFA最小牝后的各副言息如下：AaCDCDEAABEC意任_babababab^x请七：源代码#include#includeusingnamespacestd;#d

5、cfincmax100structedge{stringfirst;//边的初始结点stringcondition;//边.卜.的条件stringlast;//边的终点};intN;//NFA的边数stringpart[max];//分割子集stringmove(stringcollection,charch,edge*b)//状态集合I的a弧转换{inti,j;strings=H";for(i=0;i

6、ondition[0]==ch)s=s+b[j].last;}}if(s=="”)return”elsereturns;}boolisexist(strings,stringd)//判断子屮是开存在在某一集合{if(d!=,'"&&O<=d.find(s)&&d.find($)<=d.lcngth()-l)rcturn1;elsereturn0;intdivide(edgestringchange)//分割Y•集法进行DFA的最小化intx,m,flag=2,flag0,i,j；stringss，part()

7、maxl;flagO=flag;for(x=0;x

8、hangeJength();x++){for(m=0;m

9、j]+part[m].$ubstr(i,1);if(ss==”{partO[flag]=partO[flag]+part[m].substr(i,1);break;}}}for(j=0;j<=flag;j++){if(partO

10、[j]!=