编译实验三NFA转换成DFA和DFA化简Word文件下载.doc
《编译实验三NFA转换成DFA和DFA化简Word文件下载.doc》由会员分享，可在线阅读，更多相关《编译实验三NFA转换成DFA和DFA化简Word文件下载.doc（20页珍藏版）》请在冰点文库上搜索。
存储格式如上所示，程序开始时，从文件中读取数据以获得NFA中的各种信息。
根据子集构造法，构造相应的函数。
子集构造法伪代码如下：
初始时,
ε-closure（S0）
是
Dstates
中唯一的状态且未被标记;
while
中存在一个未标记的状态T
do
begin
标记T;
for
每个输入符号
a
U
:
=
ε-closure
（
move
（T,
a）
）;
if
没在Dstates中
then
将U作为一个未被标记的状态添加到
Dstates.
Dtran
[
T,
]
end
end
的计算
将T中所有状态压入栈stack;
将ε-closure
（T）
初始化为T;
stack不空
将栈顶元素t弹出栈;
每个这样的状态u：
从t到u有一条标记为
ε的边do
u
不在ε-closure
T
）中
将u
添加到ε-closure
将u压入栈stack中
子集构造法的流程图：
实验三
（二）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输出的功能。
程序总框图如下：
功能图如下：
四．运行结果
五.实验问题及心得
通过此次对从NFA到DFA的转化和DFA的化简的设计，使我更好的理解了NFA确定化过程的相关知识，很好的理解了子集法的演算过程。
还有DFA的化简过程有了更好地理解。
经过多次试验，在正确输入相关数据的情况下，程序能正常运行，当错误操作或输入错误数据时，程序将应错误自动关闭。
经过这次课程设计,也让我深刻的认识到实践才是最重要的。
书本只能教给我们基础知识,要怎样运用,将那些知识真正吸收,转化为自己的智慧,只有通过实践才能达到。
编译原理是一门实用性很强，对我们的专业很有帮助的科目,我将会继续努力,不断增加自己的知识面,把编译原理学习的更好。
六.附录
#include<
iostream>
string>
#defineMAXS100
usingnamespacestd;
stringNODE;
//结点集合
stringCHANGE;
//终结符集合
intN;
//NFA边数
structedge
{
stringfirst;
stringchange;
stringlast;
};
structchan
stringltab;
stringjihe[MAXS];
voidkong（inta）
inti;
for（i=0;
i<
a;
i++）
cout<
<
'
'
;
}
//排序
voidpaixu（string&
a）
inti,j;
charb;
for（j=0;
j<
a.length（）;
j++）
for（i=0;
if（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<
N;
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（）;
k;
for（j=0;
if（（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;
l;
for（j=0;
if（（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]+=b[j].last[0];
//输出
voidoutputfa（intlen,inth,chan*t）
inti,j,m;
cout<
"
I"
len;
I'
CHANGE[i]<
"
endl<
-------------------------"
endl;
h;
t[i].ltab;
m=t[i].ltab.length（）;
{
kong（8-m）;
m=t[i].jihe[j].length（）;
cout<
t[i].jihe[j];
}
voidmain（）
edge*b=newedge[MAXS];
inti,j,k,m,n,h,x,y,len;
boolflag;
stringjh[MAXS],endnode,ednode,sta;
请输入NFA各边信息（起点条件[空为*]终点），以#结束：
MAXS;
cin>
>
b[i].first;
if（b[i].first=="
#"
break;
b[i].change>
b[i].last;
N=i;
/*for（j=0;
b[j].first<
b[j].change<
b[j].last<
*/
{
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（）;
结点中属于终态的是：
cin>
endnode;
endnode.length（）;
if（NODE.find（endnode[i]）>
所输终态不在集合中，错误！
return;
//cout<
endnode="
endnode<
chan*t=newchan[MAXS];
t[0].ltab=b[0].first;
h=1;
eclouse（b[0].first[0],t[0].ltab,b）;
//求e-clouse
t[0].ltab<
for（j=0;
t[i].ltab.length（）;
for（m=0;
m<
m++）
eclouse（t[i].ltab[j],t[i].jihe[m],b）;
for（k=0;
{
//cout<
t[i].jihe[k]<
->
move（t[i],k,b）;
//求move（I,a）
t[i].jihe[k].length（）;
eclouse（t[i].jihe[k][j],t[i].jihe[k],b）;
}
for（j=0;
paixu（t[i].jihe[j]）;
//对集合排序以便比较
for（k=0;
{
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];
状态转换矩阵如下：
outputfa（len,h,t）;
//输出状态转换矩阵
//状态重新命名
string*d=newstring[h];
NODE.erase（）;
重命名：
sta=t[i].ltab;
t[i].ltab.erase（）;
t[i].ltab='
A'
+i;
NODE+=t[i].ltab;
{'
sta<
}="
t[i].ltab<
if（sta.find（endnode[j]）<
sta.length（））
d[1]=ednode+=t[i].ltab;
for（m=0;
if（sta==t[k].jihe[m]）
t[k].jihe[m]=t[i].ltab;
NODE.length（）;
if（ednode.find（NODE[i]）>
ednode.length（））
d[0]+=NODE[i];
endnode=ednode;
DFA如下：
outputfa（len,h,t）;
//输出DFA
其中终态为：
//DFA最小化
m=2;
sta.erase（）;
flag=0;
for（i=0;
m;
//cout<
d["
]="
d[i]<
I"
CHANGE[k]<
y=m;
d[i].length（）;
for（n=0;
n<
y;
n++）
{
if（d[n].find（t[NODE.find（d[i][j]）].jihe[k]）<
d[n].length（）||t[NODE.find（d[i][j]）].jihe[k].length（）==0）
{
if（t[NODE.find（d[i][j]）].jihe[k].length（）==0）
x=m;
else
x=n;
if（!
{
sta+=x+48;
}
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;
sta="
sta.erase（）;
}//k
}//i
集合划分：
cout<
{"
}"
//状态重新命名
chan*md=newchan[m];
NODE.erase（）;
md[i].ltab='
NODE+=md[i].ltab;
md[i].ltab<
if（d[i][0]==t[j].ltab[0]）
for（n=0;
t[j].jihe[k].length（））
elseif（d[n].find（t[j].jihe[k]）<
d[n].length（））
md[i].jihe[k]=md[n].ltab;
}
ednode.erase（）;
for（i=0;
for（j=0;
if（d[i].find（endnode[j]）<
d[i].length（）&
ednode.find（md[i].ltab））
ednode+=md[i].ltab;
endnode=ednode;
cout<
最小化DFA如下：
outputfa（len,m,md）;
升级会员 