实验五-DFA的最小化.docxVIP

编译原理实验报告 实验五：DFA的最小化 实验目的： 熟练掌握DFA及NFA的定义及有关概念。 理解并掌握确定的有穷自动机的最小化等算法。 实验要求： 输入： DFA。 输出： 最小化的DFA。 实验原理： 1.化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去，也就获得了状态数最小的DFA。 2.DFA的化简算法： 首先将DFA M的状态划分出终止状态集K1和非终止状态集K2。 K＝K1∪K2 由上述定义知，K1和K2是不等价的。 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。 设第i次划分已将状态集划分为k组，即： K＝K1(i)∪K2(i)∪…∪Kk(i) 对于状态集Kj(i)（j=1,2,…,k）中的各个状态逐个检查，设有两个状态Kj’、 Kj’’∈Kj(i)，且对于输入符号a，有： F（Kj，a）＝Km F（Kj，a）＝Kn 如果Km和Kn属于同一个状态集合，则将Kj’和Kj’’放到同一集合中，否则将Kj’和Kj’’分为两个集合。 重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。 若有无关状态，则将其删去。 根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。 实验内容： 程序代码如下： #includeiostream #includestring using namespace std; #define max 100 struct edge{ string first;//边的初始结点 string change;//边的条件 string last;//边的终点 }; int N;//NFA的边数 string part[max];//分割子集 //状态集合I的a弧转换 string move(string jihe,char ch,edge *b) { int i,j; string s=; for(i=0;ijihe.length();i++) { for(j=0;jN;j++) { if(b[j].first[0]==jihe[i]b[j].change[0]==ch) s=s+b[j].last; } } if(s==)return ; else return s; } //判断子串是否存在在某一集合 bool isexist(string s,string d) { if(d!=0=d.find(s)d.find(s)=d.length()-1)return 1; else return 0; } //分割子集法进行DFA的最小化 int divide(edge *b,string change) { int x,m,flag=2,flag0,i,j; string ss,part0[max]; flag0=flag; for(x=0;xchange.length();x++) { for(m=0;mflag0;m++) { for(i=0;ipart[m].length();i++) { ss=move(part[m].substr(i,1),change[x],b); for(j=0;jflag;j++) { if(isexist(ss,part[j]))part0[j]=part0[j]+part[m].substr(i,1); if(ss==) { part0[flag]=part0[flag]+part[m].substr(i,1); break; } } } for(j=0;j=flag;j++) { if(part0[j]!=part0[j]!=part[m]) { part[flag++]=part0[j]; part0[j]=; part[m]=; } else part0[j]=; } } flag0=flag; } return flag; } void main() { int i,j,flag,x; string Change;//输入符号 string ss; edge *b=new edge[max];