编译原理实验六：DFA最小化(共7页)

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

2、（2） 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。设第i次划分已将状态集划分为k组，即：KK1(i)K2(i)Kk(i)对于状态集Kj(i)（j=1,2,k）中的各个状态逐个检查，设有两个状态Kj、 KjKj(i)，且对于输入符号a，有：F（Kj'，a）KmF（Kj''，a）Kn如果Km和Kn属于同一个状态集合，则将Kj和Kj放到同一集合中，否则将Kj和Kj分为两个集合。（3） 重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。（4） 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。（5） 若

3、有无关状态，则将其删去。根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。四：数据结构与算法struct edge string first;/边的初始结点string condition;/边上的条件string last;/边的终点;string move(string collection,char ch,edge *b)/状态集合I的a弧转换int divide(edge *b,string change)/分割子集法进行DFA的最小化五：出错分析1：在数据结构的定义之中，字符与字符串的差别，本次实验室字符串而不是字符六：实验结果与分析七：源代码

4、#include<iostream>#include<string>using namespace std;#define max 100struct edge string first;/边的初始结点string condition;/边上的条件string last;/边的终点;int N;/NFA的边数string partmax;/分割子集string move(string collection,char ch,edge *b)/状态集合I的a弧转换int i,j;string s=""for(i=0;i<collection.len

5、gth();i+) for(j=0;j<N;j+)if(bj.first0=collectioni&&bj.condition0=ch) s=s+bj.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;int

6、divide(edge *b,string change)/分割子集法进行DFA的最小化int x,m,flag=2,flag0,i,j;string ss,part0max; flag0=flag;for(x=0;x<change.length();x+)for(m=0;m<flag0;m+)for(i=0;i<partm.length();i+)ss=move(partm.substr(i,1),changex,b);for(j=0;j<flag;j+)if(isexist(ss,partj)part0j=part0j+partm.substr(i,1); if(s

7、s="&")part0flag=part0flag+partm.substr(i,1);break;for(j=0;j<=flag;j+)if(part0j!=""&&part0j!=partm)partflag+=part0j;part0j=""partm=""else part0j=""flag0=flag;return flag;void main() int i,j,flag,x; string Condition;/边上的条件 string ss; edg

8、e *b=new edgemax; cout<<".编译原理实验六：DFA最小化."<<endl; cout<<"请输入DFA各边信息：起点 条件（空用&表示） 终点 并以输入#结束。"<<endl; for(i=0;i<max;i+) cin>>bi.first; if(bi.first="#")break; else cin>>bi.condition>>bi.last; N=i; cout<<"请输入该DFA的

9、终态集合："<<endl; cin>>part1; cout<<"请输入该DFA的非终态集合："<<endl; cin>>part0; cout<<"请输入此DFA状态中的边上的条件:"<<endl; cin>>Condition; flag=divide(b,Condition); cout<<"DFA最小化划分的子集如下："<<endl; for(i=0;i<flag;i+) if(parti!=

10、"")cout<<parti<<endl; cout<<"用状态A,B,C···等代替子集：" for(i=0;i<flag;i+) if(parti!="")cout<<""<<parti<<"," cout<<endl<<"则DFA最小化后的各边信息如下："<<endl; char lettersmax; char letter='A' for(i=0;i<flag;i+) if(parti!="") lettersi=letter; +letter; for(i=0;i<flag;i+) for(j=0;j<Condition.length();j+) ss=move(parti,Conditionj,b); if(parti!=""&&ss!="&")cout<<lettersi<<&quo