编译实验三NFA转换成DFA和DFA化简.docx
《编译实验三NFA转换成DFA和DFA化简.docx》由会员分享，可在线阅读，更多相关《编译实验三NFA转换成DFA和DFA化简.docx（18页珍藏版）》请在冰点文库上搜索。
编译实验三NFA转换成DFA和DFA化简
实验三
（一）NFADFA（2小时）
一.问题描述
NFAàDFA。
1.实验目的：
学会编程实现子集构造法。
2.实验任务：
存储NFA与DFA，编程实现子集构造法将NFA转换成DFA。
3.实验内容：
（1）确定NFA与DFA的存储格式，为3个以上测试NFA准备好存储文件。
（2）用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。
（3）经测试无误。
测试不易。
可求出NFA与DFA的语言集合的某个子集（如长度小于某个N），再证实两个语言集合完全相同！
（4）测试用例参考：
将下列语言用RE表示，再转换成NFA使用：
（a）以a开头和结尾的小字字母串；a（a|b|…|z）*a|a
（b）不包含三个连续的b的，由字母a与b组成的字符串；（e|b|bb）（a|ab|abb）*
（c）（aa|b）*（a|bb）*
二．算法描述
1.NFA的输入：
分别输入NFA的“字符集”、“状态集”、“开始状态”、“接受状态集”、“状态转换表”等内容，并保存在设定的变量中。
2.NFA的存储与读写：
将上述NFA的五元组保存在一个文本文件中。
存储格式如下所示（以下图中NFA为例）：
2//字符集中的字符个数（以下两行也可合并成一行）
ab//以空格分隔的字符集。
4//状态个数（以下两行也可合并成一行）
1234//状态编号。
若约定总是用从1开始的连续数字表示，则此行可省略
1//开始状态的编号。
若约定为1，则此行可省略
1//结束状态个数。
若约定为1，则此行可省略
3//结束状态的编号
321//状态1的所有出去的转换。
按字符集中的字符顺序给出，并在最左边加上一列关于e的转换。
-1表示出错状态。
多个状态用逗号分隔。
-11-1
-134
-1-13
3.基本算法描述
存储格式如上所示，程序开始时，从文件中读取数据以获得NFA中的各种信息。
根据子集构造法，构造相应的函数。
子集构造法伪代码如下：
初始时, ε-closure（S0） 是 Dstates 中唯一的状态且未被标记;
while Dstates 中存在一个未标记的状态T do begin
标记T;
for 每个输入符号 a do begin
U :
= ε-closure （ move （T, a） ）;
if U 没在Dstates中 then
将U作为一个未被标记的状态添加到 Dstates.
Dtran [ T, a ] :
= U
end
end
ε-closure 的计算
将T中所有状态压入栈stack;
将ε-closure （T） 初始化为T;
while stack不空 do begin
将栈顶元素t弹出栈;
for 每个这样的状态u：
从t到u有一条标记为 ε的边do
if u 不在ε-closure （ T ）中 do begin
将u 添加到ε-closure （ T ）;
将u压入栈stack中
end
end
子集构造法的流程图：
实验三
（二）DFA化简（2小时）
一.问题描述
DFA化简
1．实验目的：
学会编程实现等价划分法化简DFA。
2．实验任务：
先完善DFA，再化简DFA。
3．实验内容：
（1）准备3个以上测试DFA文件。
（2）DFA手动完善。
（状态转换映射要是满映射）
（3）用C或JAVA语言编写用等价划分法化简DFA的程序。
（4）经测试无误。
测试不易。
可求出两个DFA的语言集合的某个子集（如长度小于某个N），再证实两个语言集合完全相同！
（5）编写实验报告。
要求同实验一，不再详述。
二．算法描述
1. DFA的化简
得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最简的DFA[12]，也就是说，NFA转化为DFA之后，还需要化简，也就是最小化。
2.化简的理论基础
DFA的化简是指：
寻找一个状态数最少的DFA M，使得L（M）=L（M’）。
化简的方法是消去DFA M中的多余状态（或无用状态），合并等价状态。
DFA中的多余状态是指这样的状态：
从开始状态出发，读入任何输入串都不能到达的那个状态；或者从这个状态没有通路到达终态。
两个状态S 和T等价是指：
如果从状态S出发能读出某个字W而停于终态，从T出发也能读出同样的字W而停于终态；反之，从T出发能读出同样的字W而停于终态，从S出发也能读出某个字W而停于终态。
3.化简的基本思想
化简DFA的基本思想是指导它的状态分成一些互不相交的子集，每一个子集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，最后将不能区别的每个子集用一个状态来做代表[13-15]，这种方法称为“分割法”。
具体过程是：
（1）将M的所有状态分成两个子集——终态集和非终态集；
（2）考察每一个子集，若发现某子集中的状态不等价，将其划分为两个集合；
（3）重复第
（2）步，继续考察已得到的每一个子集，直到没有任何一个子集需要继续划分为止。
这时DFA的状态被分成若干个互不相交的子集。
（4）从每个子集中选出一个状态做代表即可得到最简的DFA。
三．程序分析
通过本设计所要求达到的目的是：
充分理解和掌握NFA，DFA以及NFA确定化过程的相关概念和知识，理解和掌握子集法的相关知识和应用，现在需要编程实现对输入NFA转换成DFA输出的功能。
程序总框图如下：
功能图如下：
4．运行结果
5.实验问题及心得
通过此次对从NFA到DFA的转化和DFA的化简的设计，使我更好的理解了NFA确定化过程的相关知识，很好的理解了子集法的演算过程。
还有DFA的化简过程有了更好地理解。
经过多次试验，在正确输入相关数据的情况下，程序能正常运行，当错误操作或输入错误数据时，程序将应错误自动关闭。
经过这次课程设计,也让我深刻的认识到实践才是最重要的。
书本只能教给我们基础知识,要怎样运用,将那些知识真正吸收,转化为自己的智慧,只有通过实践才能达到。
编译原理是一门实用性很强，对我们的专业很有帮助的科目,我将会继续努力,不断增加自己的知识面,把编译原理学习的更好。
6.附录
#include
#include
#defineMAXS100
usingnamespacestd;
stringNODE;//结点集合
stringCHANGE;//终结符集合
intN;//NFA边数
structedge
{
stringfirst;
stringchange;
stringlast;
};
structchan
{
stringltab;
stringjihe[MAXS];
};
voidkong（inta）
{
inti;
for（i=0;icout<<'';
}
//排序
voidpaixu（string&a）
{
inti,j;
charb;
for（j=0;jfor（i=0;iif（NODE.find（a[i]）>NODE.find（a[i+1]））
{
b=a[i];
a[i]=a[i+1];
a[i+1]=b;
}
}
voideclouse（charc,string&he,edgeb[]）
{
intk;
for（k=0;k{
if（c==b[k].first[0]）
if（b[k].change=="*"）
{
if（he.find（b[k].last）>he.length（））
he+=b[k].last;
eclouse（b[k].last[0],he,b）;
}
}
}
voidmove（chan&he,intm,edgeb[]）
{
inti,j,k,l;
k=he.ltab.length（）;
l=he.jihe[m].length（）;
for（i=0;ifor（j=0;jif（（CHANGE[m]==b[j].change[0]）&&（he.ltab[i]==b[j].first[0]））
if（he.jihe[m].find（b[j].last[0]）>he.jihe[m].length（））
he.jihe[m]+=b[j].last[0];
for（i=0;ifor（j=0;jif（（CHANGE[m]==b[j].change[0]）&&（he.jihe[m][i]==b[j].first[0]））
if（he.jihe[m].find（b[j].last[0]）>he.jihe[m].length（））
he.jihe[m]+=b[j].last[0];
}
//输出
voidoutputfa（intlen,inth,chan*t）
{
inti,j,m;
cout<<"I";
for（i=0;icout<<'I'<cout<for（i=0;i{
cout<<''<m=t[i].ltab.length（）;
for（j=0;j{
kong（8-m）;
m=t[i].jihe[j].length（）;
cout<}
cout<}
}
voidmain（）
{
edge*b=newedge[MAXS];
inti,j,k,m,n,h,x,y,len;
boolflag;
stringjh[MAXS],endnode,ednode,sta;
cout<<"请输入NFA各边信息（起点条件[空为*]终点），以#结束：
"<for（i=0;i{
cin>>b[i].first;
if（b[i].first=="#"）
break;
cin>>b[i].change>>b[i].last;
}
N=i;
/*for（j=0;jcout<for（i=0;i{
if（NODE.find（b[i].first）>NODE.length（））
NODE+=b[i].first;
if（NODE.find（b[i].last）>NODE.length（））
NODE+=b[i].last;
if（（CHANGE.find（b[i].change）>CHANGE.length（））&&（b[i].change!
="*"））
CHANGE+=b[i].change;
}
len=CHANGE.length（）;
cout<<"结点中属于终态的是：
"<cin>>endnode;
for（i=0;iif（NODE.find（endnode[i]）>NODE.length（））
{
cout<<"所输终态不在集合中，错误！
"<return;
}
//cout<<"endnode="<chan*t=newchan[MAXS];
t[0].ltab=b[0].first;
h=1;
eclouse（b[0].first[0],t[0].ltab,b）;//求e-clouse
//cout<for（i=0;i{
for（j=0;jfor（m=0;meclouse（t[i].ltab[j],t[i].jihe[m],b）;//求e-clouse
for（k=0;k{
//cout<";
move（t[i],k,b）;//求move（I,a）
//cout<for（j=0;jeclouse（t[i].jihe[k][j],t[i].jihe[k],b）;//求e-clouse
}
for（j=0;j{
paixu（t[i].jihe[j]）;//对集合排序以便比较
for（k=0;k{
flag=operator==（t[k].ltab,t[i].jihe[j]）;
if（flag）
break;
}
if（!
flag&&t[i].jihe[j].length（））
t[h++].ltab=t[i].jihe[j];
}
}
cout<"<outputfa（len,h,t）;//输出状态转换矩阵
//状态重新命名
string*d=newstring[h];
NODE.erase（）;
cout<"<for（i=0;i{
sta=t[i].ltab;
t[i].ltab.erase（）;
t[i].ltab='A'+i;
NODE+=t[i].ltab;
cout<<'{'<for（j=0;jif（sta.find（endnode[j]）d[1]=ednode+=t[i].ltab;
for（k=0;kfor（m=0;mif（sta==t[k].jihe[m]）
t[k].jihe[m]=t[i].ltab;
}
for（i=0;iif（ednode.find（NODE[i]）>ednode.length（））
d[0]+=NODE[i];
endnode=ednode;
cout<"<outputfa（len,h,t）;
//输出DFA
cout<<"其中终态为：
"<m=2;
sta.erase（）;
flag=0;
for（i=0;i{
//cout<<"d["<for（k=0;k{
//cout<<"I"<y=m;
for（j=0;j{
for（n=0;n{
if（d[n].find（t[NODE.find（d[i][j]）].jihe[k]）{
if（t[NODE.find（d[i][j]）].jihe[k].length（）==0）
x=m;
else
x=n;
if（!
sta.length（））
{
sta+=x+48;
}
else
if（sta[0]!
=x+48）
{
d[m]+=d[i][j];
flag=1;
d[i].erase（j,1）;
//cout<j--;
}
break;
//跳出n
}
}//n
}//j
if（flag）
{
m++;flag=0;
}
//cout<<"sta="<sta.erase（）;
}//k
}//i
cout<";
for（i=0;icout<<"{"<cout<//状态重新命名
chan*md=newchan[m];
NODE.erase（）;
cout<"<for（i=0;i{
md[i].ltab='A'+i;
NODE+=md[i].ltab;
cout<<"{"<}
for（i=0;ifor（k=0;kfor（j=0;j{
if（d[i][0]==t[j].ltab[0]）
{
for（n=0;n{
if（!
t[j].jihe[k].length（））
break;
elseif（d[n].find（t[j].jihe[k]）{
md[i].jihe[k]=md[n].ltab;
break;
}
}
break;
}
}
ednode.erase（）;
for（i=0;ifor（j=0;jif（d[i].find（endnode[j]）ednode+=md[i].ltab;
endnode=ednode;
cout<"<outputfa（len,m,md）;
cout<<"其中终态为：
"<}
升级会员 