NFA到DFA转化Word文档格式.doc
《NFA到DFA转化Word文档格式.doc》由会员分享，可在线阅读，更多相关《NFA到DFA转化Word文档格式.doc（15页珍藏版）》请在冰点文库上搜索。
Σ—输入字母表
δ—映射函数（也称状态转换函数）
S×
Σ→S
δ（s,a）=S’,S,S’∈S,a∈Σ
S0—初始状态S0∈S
Z—终止状态集ZÍ
S
1.2NFA和DFA之间的联系
在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。
这种不确定性给识别过程带来的反复，无疑会影响到FA的工作效率。
而DFA则是确定的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必要的。
2.概要设计
通过本课程设计教学所要求达到的目的是：
充分理解和掌握NFA，DFA以及NFA确定化过程的相关概念和知识，理解和掌握子集法的相关知识和应用，编程实现对输入NFA转换成DFA输出的功能。
程序总框图如图1所示：
总控模块
NFA图结构
状态转换表机构
图操作
初始化状态转换矩阵
状态转换操作
图1程序总框图
3.详细设计
3.1子集构造法
已证明：
非确定的有限自动机与确定的有限自动机从功能上来说是等价的，也就是说，我们能够从：
NFAM’DFAM
使得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是NFAM’的状态集的一个子集,a∈Σ
定义:
Ia=ε-closure（J）
其中J=∪δ（s,a）
——J是从状态子集I中的每个状态出发,经过标记为a的弧而达到的状态集合。
——Ia是状态子集,其元素为J中的状态,加上从J中每一个状态出发通过ε弧到达的状态。
给定如图2所示的NFA:
b
ε
a
1
2
3
4
图2
与之等价的DFA如图3：
{0，1}
{2，4}
{4}
{3}
图3
3.2具体转换过程
为了说明跟清晰，我们使用实例说明，构造正规式101（0|1）*011的DFA？
解：
首先构造相应的NFA，如图4所示：
5
6
4
7
8
图4
将其写成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）＝6
δ（6，1）＝7
δ（7，1）＝8
它所对应的状态转换矩阵如表1：
表1
状态
根据NFA转化为DFA的子集法转换法进行转换，对应的状态转换矩阵见表2：
表2
I
I0
I1
{0}
{ε}
{1}
{2}
{3，4，5}
{4，5，6}
{4，5}
{4，5，7}
{4，5，8}
对上表重新命名后的状态转换矩阵见表3：
表3
M=（{0，1，2，3，4，5，6，7}，{0，1}，δ，0，{5}）
δ（3，0）＝4δ（3，1）＝5
δ（4，0）＝4δ（4，1）＝6
δ（5，0）＝4δ（5，1）＝5
δ（6，0）＝4δ（6，1）＝7
δ（7，0）＝4δ（7，1）＝5
与表3对应的状态转换图如图5所示：
图5
这样就完成了从正规表达式101（0|1）*011到DFA的转化。
3.3程序设计
3.3.1常量定义
#defineMAX10
#defineNumMaxChar10
#defineNumMAXTN10
#defineINFINIT32767
3.3.2数据结构定义
NFA图结构定义如下：
typedefstructedge
{//边
intdest;
charcost;
structedge*link;
//指向下一边
}*Edge;
typedefstructvertex
{//顶点
chardata;
//状态
Edgeadj;
//边
}*Vertex;
typedefstructgraph
{//图
VertexNodeTable;
intNumVertex;
intMaxNumVertex;
intNumEdge;
}*Graph;
状态转换表机构定义如下：
typedefstructtablenode
{//转换表节点
charnewname;
//新命名
charch[MAX];
//顶点集合
}*TableNode;
typedefstructtablequeue
{//转换表列
TableNodeTN[MAX];
//转换表节点数组
chartransword;
//转换条件
intNumTn;
//添加的顶点数
}*TableQueue;
typedefstructtransmatrix
{//状态转换矩阵
TableQueueTQ;
//转换表列组
inttransnum;
//转换表列数
}*TranMatrix;
3.3.3主要函数流程图
voidSmove函数流程图如图6所示：
非0
开始
inti,j,k=0,check,len;
Edgep;
while（t2[k]!
='
\0'
）
k++;
for（i=0;
i<
MAX;
i++）
for（j=0;
j<
g->
NumVertex;
j++）
if（g->
NodeTable[j].data==t1[i]）
{p=g->
NodeTable[j].adj;
while（p!
=NULL）
{if（p->
cost==transword）
{check=CheckChar（t2,g->
NodeTable[p->
dest].data）;
if（check==1）
{t2[k]=g->
dest].data;
k++;
}
p=p->
link;
}
else
}
}
len=k；
BubbleSort（t2,k）;
结束
图6
voidShow_TranMatrix函数流程图如图7所示：
inti,j,k;
printf（"
状态转换矩阵:
\n"
）;
=TM->
transnum;
printf（"
转换字符:
%c"
TM->
TQ[j].transword）;
for（k=0;
k<
k++）
if（TM->
TQ[j].TN[k]->
newname=='
）printf（"
NULL"
elseprintf（"
%c:
"
newname）;
TM->
ch[i]!
;
{ printf（"
%c"
ch[i]）;
}
ch[0]=='
NULL"
"
结束
图7
4.测试分析
用正规表达式101（0|1）*011进行测试。
首先在“请输入NFA的总状态数”后输入“9”，接着在“请依次输入NFA的状态名称:
”后依次输入0~8，在“请输入NFA的边数:
”后输入“10”，然后依次输入各起始状态、接受字符和到达状态，接受字符为2，依次为0、1，新状态依次命名为0~7，程序最后结果正确。
程序运行截图如下：
5.用户手册
本程序应在MicrosoftVisualC++6.0下运行。
NFA的确定化是编译过程中一个重要的部分，由于本程序的输入很多，而且有多种格式的输入，所以输入时必须非常小心细致。
对于状态转换矩阵的表示，冒号前的是新状态名，冒号后的是旧状态名。
对于转化后的DFA表示，3个数据分别表示为起始状态、接受字符和到达状态，例如（0,1,1）表示为新状态0接受字符1到达新字符状态1。
运行结果因为转换字符输入顺序的不同，得出的结果有可能与笔算得出的顺序有所不同，但是结果依然是正确。
14
升级会员 