实验五-DFA的最小化

《实验五-DFA的最小化》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、编译原理实验报告实验五：DFA的最小化实验目的：1.熟练掌握DFA及NFA的定义及有关概念。2.理解并掌握确定的有穷自动机的最小化等算法。实验要求：输入：DFAo输岀：最小化的DFAo实验原理：1•化简DFA关键在于把它的状态集分成一些两两互不和交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去,也就获得了状态数最小的DFAo2.DFA的化简算法：(1)首先将DFAM的状态划分出终止状态集Ki和非终止状态集K2oK

2、=KiUK2由上述定义知，K1和《2是不等价的。(2)对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。设第i次划分已将状态集划分为k组，即：K=K1(i)UK2(i,U...UKk(i)对于状态集Kj⑴(何2…,k)中的各个状态逐个检查，设有两个状态KjKj〃WKF，且对于输入符号a,有：F(K/,a)=KmF(Kj",a)=心如果褊和Kn属于同一个状态集合，则将Kf和Kj〃放到同一集合中，否则将Kf和Kj〃分为两个集合。(3)重复第(2)步，直到每一个集合不能再划分为止，此吋每个状态集合屮的状态均是等价的。(

3、4)合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。(5)若有无关状态，则将其删去。根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。实验内容:程序代码如下：#include#includeusingnamespacestd;#definemax100structedge{stringfirst;//边的初始结点stringchange;//边的条件stringlast;//边的终点}；intN;//NFA的边数strin

4、gpart[max];〃分割子集〃状态集合I的a弧转换stringmove(stringjihe,charch,edge*b){inti,j；strings=,,u;for(i=0;i

5、=""&&0<=d.find(s)&&d.find(s)<=d.length()-l)return1;elsereturn0;}〃分割子集法进行DFA的最小化intdivide(edge*b,stringchange)intx,m,flag=2,flag0,i,j;stringss,partO[max];flagO=flag;for(x=0;x

6、tr(i,l),change[x],b);for(j=0;j

7、"";}elsepartO[j]="";}}flagO=flag;}returnflag;}voidmain(){inti,j,flag,x;stringChange;//输入符号stringss;"«endl;edge*b=newedge[max];cout«"请输入DFA各边信息：起点条件(空用&表示)终点，以输入#结束。for(i=0;i>b[i].first;if(b[i].first=="#")break;elsecin>>b[i].change»b[i]」ast;}N=i;cout«"

8、请输入该DFA的终态集合：”《endl;cin»part[l];cout«"请输入该DFA的非终态集合：”《endl;cin»part[O];cout«"请输入此DFA状态中的输入符号即边上的条件:H«endl;cin>>Change;flag=divide(b,Change);cout«