编译原理实验六DFA最小化.docx
《编译原理实验六DFA最小化.docx》由会员分享，可在线阅读，更多相关《编译原理实验六DFA最小化.docx（8页珍藏版）》请在冰点文库上搜索。
编译原理实验六DFA最小化
实验六：
DFA最小化
一：
要求
输入：
DFA。
输出：
最小化的DFA。
二：
实验目的
1.熟练掌握DFA与NFA的定义与有关概念。
2.理解并掌握确定的有穷自动机的最小化等算法。
三：
实验原理
1.化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去，也就获得了状态数最小的DFA。
2.DFA的化简算法：
（1）首先将DFAM的状态划分出终止状态集K1和非终止状态集K2。
K＝K1∪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〕＝Km
F〔Kj''，a〕＝Kn
如果Km和Kn属于同一个状态集合，如此将Kj’和Kj’’放到同一集合中，否如此将Kj’和Kj’’分为两个集合。
（3）重复第〔2〕步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。
（4）合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。
（5）假如有无关状态，如此将其删去。
根据以上方法就将确定有限自动机进展了简化，而且简化后的自动机是原自动机的状态最少的自动机。
四：
数据结构与算法
structedge{
stringfirst;//边的初始结点
stringcondition;//边上的条件
stringlast;//边的终点
};
stringmove（stringcollection,charch,edge*b）//状态集合I的a弧转换
intdivide（edge*b,stringchange）//分割子集法进展DFA的最小化
五：
出错分析
1：
在数据结构的定义之中，字符与字符串的差异，本次实验室字符串而不是字符
六：
实验结果与分析
七：
源代码
#include
#include
usingnamespacestd;
#definemax100
structedge{
stringfirst;//边的初始结点
stringcondition;//边上的条件
stringlast;//边的终点
};
intN;//NFA的边数
stringpart[max];//分割子集
stringmove（stringcollection,charch,edge*b）//状态集合I的a弧转换
{
inti,j;
strings="";
for（i=0;i{
for（j=0;j{
if（b[j].first[0]==collection[i]&&b[j].condition[0]==ch）
s=s+b[j].last;
}
}
if（s==""）return"&";
elsereturns;
}
boolisexist（strings,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{
for（m=0;m{
for（i=0;i{
ss=move（part[m].substr（i,1）,change[x],b）;
for（j=0;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]="";
}
elsepart0[j]="";
}
}
flag0=flag;
}
returnflag;
}
voidmain（）
{
inti,j,flag,x;
stringCondition;//边上的条件
stringss;
edge*b=newedge[max];
cout<<"...................编译原理实验六：
DFA最小化...................."<cout<<"请输入DFA各边信息：
起点条件〔空用&表示〕终点并以输入#完毕。
"<for（i=0;i{
cin>>b[i].first;
if（b[i].first=="#"）break;
else
cin>>b[i].condition>>b[i].last;
}
N=i;
cout<<"请输入该DFA的终态集合：
"<cin>>part[1];
cout<<"请输入该DFA的非终态集合：
"<cin>>part[0];
cout<<"请输入此DFA状态中的边上的条件:
"<cin>>Condition;
flag=divide（b,Condition）;
cout<<"DFA最小化划分的子集如下：
"<for（i=0;i{
if（part[i]!
=""）cout<}
cout<<"用状态A,B,C···等代替子集：
";
for（i=0;i{
if（part[i]!
=""）cout<<"{"<}
cout<"<charletters[max];
charletter='A';
for（i=0;i{
if（part[i]!
=""）
{
letters[i]=letter;
++letter;
}
}
for（i=0;ifor（j=0;j{
ss=move（part[i],Condition[j],b）;
if（part[i]!
=""&&ss!
="&"）cout<for（x=0;xif（isexist（ss.substr（0,1）,part[x]））cout<}
system（"pause"）;
}
升级会员 