NFA转化为DFA的转换算法及实现Word下载.docx
《NFA转化为DFA的转换算法及实现Word下载.docx》由会员分享，可在线阅读，更多相关《NFA转化为DFA的转换算法及实现Word下载.docx（22页珍藏版）》请在冰点文库上搜索。
4程序设计 14
4.1程序分析 14
4.1.1流程图 14
4.1.2子集构造法 16
4.2具体的转换过程 18
1前言
1.1选题的依据和必要性
由于很多计算机系统都配有多个高级语言的编译程序，对有些高级语言甚至配置了几个不同性质的编译程序。
从功能上看，一个编译程序就是一个语言翻译程序。
语言翻译程序把源语言书写的程序翻译成目标语言的等价程序。
经过编译程序的设计可以大大提高学生的编程能力。
编译程序的工作过程通常是词法分析、语法分析、语义分析、代码生成、代码优化[1]。
由于现在有很多词法分析程序工具都是基于有穷自动机的，而词法分析又是语法分析的基础[2]，所以我们有必要进行有穷自动机的确定化和最小化。
1.2课题意义
编译程序的这些过程的执行先后构成了编译程序的逻辑结构[3]。
有穷自动机
（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具[4]。
NFA转化为DFA的理论在词法构造至整个编译器构造过程中起着至关重要的作用，同时它们被广泛应用于计算机科学的各个领域，它们与计算机其它学科也有着密切的联系。
2NFA转化为DFA的算法及实现
编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。
内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。
进行NFA转换为DFA的词法分析和语法分析，首先要对目标对象有有所了解，这就需要对NFA、DFA进一步了解。
2.1基本定义
NFA，也称不确定的有穷自动机，是由一个五元式定义的数学模型，特点是它的不确定性，即在当前状态下，读入同一个字符，可能有多个下一状态。
DFA，也称确定的有穷自动机，也是由一个五元式定义的数学模型，相对的特点是它的确定性，即在当前状态下，读入同一个字符，最多有一个后继状态。
2.1.1NFA的概念
NFA（nondeterministicfinite-stateautomata）即非确定有限自动机,
一个非确定的有限自动机NFAM’是一个五元式:
NFA M’=（S,Σ∪{ε},δ,S0, F）
其中 S—有限状态集
Σ∪{ε}—输入符号加上ε,即自动机的每个结点所射出的弧可以是Σ中一个字符或是ε.
S0—初态集 F—终态集
δ—转换函数 S×
Σ∪{ε}→2S
1
S
Z
P
（2S--S的幂集—S的子集构成的集合）状态转换图如图2.1.1：
0，1
图2.1.1 NFA状态转换图
2.1.2DFA的概念
DFA（deterministicfinite-stateautomata）即确定有限自动机，一个确定的有限自动机DFAM是一个五元式:
M=（S,Σ，δ,S0,Z）
其中:
S —有限状态集Σ—输入字母表
δ—映射函数（也称状态转换函数）
a a
P a，
P b a Z
b P
b
图2.1.2 DFA状态转换图
2.1.3NFA与DFA的矩阵表示
一个NFA或者DFA还可以用一个矩阵[5]表示，矩阵也可以说是状态转换表，它的优点是可以快速访问给定的状态在给定的输入字符时能转换到的状态集。
矩阵，每个状态一行，每个输入符号和ε（如果有需要的）各占一列，表的第i行中与输入符号a对应的表项是一个状态集合，表示NFA或者DFA在状态i输入a时所能到达的状态集合（DFA的集合唯一），即δ（i，a）[6]。
（7）
如图2.1.1可用表2.3.1.表示：
表2.3.1NFA状态转换表
输入
状态
{P}
{S，Z}
{}
{Z}
如图2.1.2可用表2.3.2表示：
表2.3.2DFA状态转换表
a
2
3
2.1.4NFA向DFA的转换的思路
从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：
DFA的每一个状态对应NFA的一组状态DFA使用它的状态记录在NFA读入一个输入符号后可能达到的所有状态[4]。
2.2NFA和DFA之间的联系
在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。
这种不确定性给识别过程带来的反复，无疑会影响到FA的工作效率。
而DFA则是确定的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必要的。
3DFA的化简
得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最简的DFA[12]，也就是说，NFA转化为DFA之后，还需要化简，也就是最小化。
3.1化简的理论基础
DFA的化简是指：
寻找一个状态数最少的DFA M，使得L（M）=L（M’）。
化简的方法是消去DFA M中的多余状态（或无用状态），合并等价状态。
DFA中的多余状态是指这样的状态：
从开始状态出发，读入任何输入串都不能到达的那个状态；
或者从这个状态没有通路到达终态。
两个状态S 和T等价是指：
如果从状态S出发能读出某个字W而停于终态，
从T出发也能读出同样的字W而停于终态；
反之，从T出发能读出同样的字W而停于终态，从S出发也能读出某个字W而停于终态。
3.2化简的基本思想
化简DFA的基本思想是指导它的状态分成一些互不相交的子集，每一个子集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，最后将不能区别的每个子集用一个状态来做代表[13-15]，这种方法称为“分割法”。
具体过程是：
（1）将M的所有状态分成两个子集——终态集和非终态集；
（2）考察每一个子集，若发现某子集中的状态不等价，将其划分为两个集合；
（3）重复第
（2）步，继续考察已得到的每一个子集，直到没有任何一个子集需要继续划分为止。
这时DFA的状态被分成若干个互不相交的子集。
（4）从每个子集中选出一个状态做代表即可得到最简的DFA。
3.3化简的代码实现#include<
iostream>
#include<
string>
#defineMAXS100usingnamespacestd;
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;
i++）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;
i++）for（j=0;
j++）
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;
（he.jihe[m][i]==b[j].first[0]））
he.jihe[m].length（））
he.jihe[m]+=b[j].last[0];
//输出
voidoutputfa（intlen,inth,chan*t）
inti,j,m;
cout<
"
I"
len;
i++）cout<
I'
CHANGE[i]<
"
endl<
"
endl;
h;
t[i].ltab;
m=t[i].ltab.length（）;
for（j=0;
kong（8-m）;
m=t[i].jihe[j].length（）;
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;
cin>
b[i].change>
b[i].last;
}N=i;
/*for（j=0;
j++）cout<
b[j].first<
b[j].change<
b[j].last<
*/for（i=0;
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（）;
结点中属于终态的是：
endnode;
endnode.length（）;
i++）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<
t[i].ltab.length（）;
j++）for（m=0;
m<
m++）eclouse（t[i].ltab[j],t[i].jihe[m],b）;
//求e-clousefor（k=0;
t[i].jihe[k]<
->
move（t[i],k,b）;
//求move（I,a）
t[i].jihe[k].length（）;
j++）eclouse（t[i].jihe[k][j],t[i].jihe[k],b）;
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<
j++）if（sta.find（endnode[j]）<
sta.length（））d[1]=ednode+=t[i].ltab;
for（m=0;
m++）if（sta==t[k].jihe[m]）
t[k].jihe[m]=t[i].ltab;
NODE.length（）;
i++）if（ednode.find（NODE[i]）>
ednode.length（））d[0]+=NODE[i];
endnode=ednode;
DFA如下：
//输出DFA
其中终态为：
//DFA最小化
m=2;
sta.erase（）;
flag=0;
m;
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;
elsex=n;
sta.length（））
sta+=x+48;
elseif（sta[0]!
=x+48）
d[m]+=d[i][j];
flag=1;
d[i].erase（j,1）;
j--;
//跳出n
}//n
}//jif（flag）
{m++;
flag=0;
sta="
sta.erase（）;
}//k
}//i
集合划分：
{"
}"
chan*md=newchan[m];
md[i].ltab='
NODE+=md[i].ltab;
md[i].ltab<
i++）for（k=0;
k++）for（j=0;
if（d[i][0]==t[j].ltab[0]）
t[j].jihe[k].length（））break;
elseif（d[n].find（t[j].jihe[k]）<
d[n].length（））
md[i].jihe[k]=md[n].ltab;
break;
ednode.erase（）;
if（d[i].find（endnode[j]）<
d[i].length（）&
ednode.find（md[i].ltab））ednode+=md[i].ltab;
最小化DFA如下：
outputfa（len,m,md）;
4程序设计
通过本设计所要求达到的目的是：
充分理解和掌握NFA，DFA以及NFA确定化过程的相关概念和知识，理解和掌握子集法的相关知识和应用，现在需要编程
[16-18]实现对输入NFA转换成DFA输出的功能。
4.1程序分析
4.1.1流程图
程序总框图如图4.1所示：
NFA图结构
状态转换表
总模块
DFA图结构
初始化状态转换矩阵
状态转换操作
图4.1.1程序总框图
初步转化为DFA
开始
输入NFA，初始化
NFA
结束
重命名化简
图4.1.2功能图
4.1.2子集构造法
已证明：
非确定的有限自动机与确定的有限自动机从功能上来说是等价的，也就是说，我们能够从：
NFA M’ DFA M
使得 L（M）=L（M’）
为了使得NFA确定化，我们首先给出两个定义：
定义1:
集合I的ε-闭包：
令I是一个状态集的子集，定义ε-closure（I）为：
1）若s∈I，则s∈ε-closure（I）；
2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。
状态集ε-closure（I）称为I的ε-闭包
定义2:
令I是NFA M’的状态集的一个子集, a∈Σ定义:
Ia=ε-closure（J）
其中J=∪δ（s,a）
——J是从状态子集I中的每个状态出发,经过标记为a的弧而达到的状态集合。
——Ia是状态子集,其元素为J中的状态,加上从J中每一个状态出发通过
ε弧到达的状态。
给定如图2所示的NFA:
ε
4
图4.1.3
与之等价的DFA如图3：
{0，1
{3}
{2，4
{4}
图4.1.4
求开始状态闭包
集合C中存在
尚未被标记子集
是
否
将Ｕ加入Ｃ中
对子集Ｔ中的每个输入字母求Ｕ＝Ｉa子集
标记Ｔ
标记Ｆ令它为集合C中的唯一成员
图4.1.5子集构造法的流程图
4.2具体的转换过程
为了说明跟清晰，我们使用实例说明，构造正规式101（0|1）*011的DFA？
解：
首先构造相应的NFA，如图4.2.1所示：
0 1 2
5 6 7 8
图4.2.1
将其写成M五元式则为：
M=（{0，1，2，3，4，5，6，7，8}，{0，1},δ，0，{8}）其中δ为：
δ（0，1）＝1δ（1，0）＝2δ（2，1）＝3δ（3，ε）＝4
δ（4，ε）＝5 δ（4，0）＝4 δ（4，1）＝4δ（5，0）＝
升级会员 