编译原理实验六：dfa最小化

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

1、实用标准文案实验六：DFA最小化一：要求输入：DFA。输出：最小化的DFA。二：实验目的1.熟练掌握DFA及NFA的定义及有关概念。2.理解并掌握确定的有穷自动机的最小化等算法。三：实验原理1.化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去，也就获得了状态数最小的DFA。2.DFA的化简算法：（1）首先将DFAM的状态划分出终止状态集K1和非终止状态集K2。K＝K1∪

2、K2由上述定义知，K1和K2是不等价的。（2）对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。设第i次划分已将状态集划分为k组，即：K＝K1(i)∪K2(i)∪…∪Kk(i)对于状态集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）步，直到每一个集合不能再划分为止，此时每个状态集合

3、中的状态均是等价的。（4）合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。（5）若有无关状态，则将其删去。根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。精彩文档实用标准文案四：数据结构与算法structedge{stringfirst;//边的初始结点stringcondition;//边上的条件stringlast;//边的终点};stringmove(stringcollection,charch,edge*b)//状态集合I的a弧转换intdivide

4、(edge*b,stringchange)//分割子集法进行DFA的最小化五：出错分析1：在数据结构的定义之中，字符与字符串的差别，本次实验室字符串而不是字符精彩文档实用标准文案六：实验结果与分析精彩文档实用标准文案七：源代码#include#includeusingnamespacestd;#definemax100structedge{stringfirst;//边的初始结点stringcondition;//边上的条件stringlast;//边的终点};intN;//NFA的边数str

5、ingpart[max];//分割子集stringmove(stringcollection,charch,edge*b)//状态集合I的a弧转换{inti,j;strings="";for(i=0;i

6、stringd)//判断子串是否存在在某一集合{if(d!=""&&0<=d.find(s)&&d.find(s)<=d.length()-1)return1;elsereturn0;}intdivide(edge*b,stringchange)//分割子集法进行DFA的最小化{intx,m,flag=2,flag0,i,j;精彩文档实用标准文案stringss,part0[max];flag0=flag;for(x=0;x

7、part[m].length();i++){ss=move(part[m].substr(i,1),change[x],b);for(j=0;j

8、art[flag++]=part0[j];part0[j]="";part[m]="";}elsepart0[j]="";}}flag0=flag;}returnflag;}voidmain(){inti,j,flag,x;stringCondition;//边