欢迎来到天天文库
浏览记录
ID:20466571
大小:69.08 KB
页数:6页
时间:2018-10-13
《编译原理实验六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;i6、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;x8、hangeJength();x++){for(m=0;m9、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(partO10、[j]!=
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;x8、hangeJength();x++){for(m=0;m9、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(partO10、[j]!=
8、hangeJength();x++){for(m=0;m9、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(partO10、[j]!=
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]!=
此文档下载收益归作者所有