NFA转DFA.docx

NFA转DFA.docx

《NFA转DFA.docx》由会员分享，可在线阅读，更多相关《NFA转DFA.docx（21页珍藏版）》请在冰点文库上搜索。

NFA转DFA

编译方法实验报告

实验名称：

子集构造法实现NFA的确定化

实验要求

1.功能：

利用子集构造法实现NFA到DFA的转换

2.输入NFA

NFA输入格式参见图1中的test.txt，对应书中第67页图3.24的NFA状态转换图。

其中，第一列表示状态名，第二列和第三列分别表示输入字符a和b所到达的状态。

图1.输入的NFA（test.txt）

3.输出DFA

DFA输入格式参见图2中的output.txt。

其中，第一列表示输入状态名，第二列表示重新命名的状态名，第三列和第四列分别表示输入字符a和b所到达的状态。

图2.输出的DFA（output.txt）

4.确定各个子程序的功能并画出流程图

5.设计子集构造算法

6.编码实现NFA确定化程序

采用文本输入和输出的方式。

程序从名为“test.txt”的文件中读入代表NFA状态的数据，将确定化后的结果保存到“output.txt”中。

7.设计3-5个NFA测试实例，检验程序能否输出正确的DFA。

8.报告内容包括：

子集构造算法，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等

子集构造法NFA确定化的算法思想

1.1NFA的确定化（子集构造法）

即将NFAM=（S，∑，f，

，Z）DFA

=（

，∑，

）

①.初始时,ε-closure（S0）是state中唯一的状态且未被标记;

②.whilestates中存在一个未标记的状态Tdobegin

标记T;

for每个输入符号adobegin

U:

=ε-closure（move（T,a））;

ifU没在state中then

将U作为一个未被标记的状态添加到state

f[T,a]:

=U

end

end

③将含有NFA终态的子集加入

中

④重新命名S’和Z’中的状态，整理f’。

1.2NFA转DFA实现

这里，为直观显示上面所述算法的而实现，可直观看图1所示的NFA状态转化图，其等价的DFA状态转化图如图2所示。

图1NFA状态转换图

与之等价的DFA如图2：

图2DFA状态转换图

书上所示例子的状态标的转换如图3所示，简单明了，开始由S’未标记的状态开始，根据子集构造法实现NFA确定化为DFA。

详细设计说明

2.1主要用到的数据结构定义

在NFA中，采取用图的结构在存储转换信息，用数字标记转换状态的以及记录状态的个数（即图中结点的个数），边的权值（用来表示当前状态识别的字符到达下一状态）为方便起见，用数字标记。

typedefstructarcnode//图的边信息

{

intadjvex;

intweight;//边所对应的权值（在这为到达下一状态所识别的数字）

structarcnode*next;

}arcnode;

typedefstructvnode//图的结点类型定义

{

vertypedata;

arcnode*next;

}vnode,adjlist[max];

typedefstruct//图的定义

{

adjlista;

intvexnum;

}Graph;

2.2主要函数的说明

intchange（Graphg,charc）：

将图中结点转化为对应下标（0,1,2,3…..）

voidcreG（Graph&g,FILE*fpr）：

从文件中读取信息，将信息转换成图的存储形式

statechanging（states,intn,Graphg）：

求当前状态集合的转移集合，即求s状态识别n之后的状态集合

intequalSet（statem,staten）：

比较两个状态的set集合内容是否相等，若相等，返回数字1，否则，返回数字0。

oidinStates（state&s）：

判断当前状态是否在States数组中存在，若存在，进行改名；若不存在，改名后加入States数组

voidNFATODFA（Graphg,FILE*fpw）：

NFA转DFA，在变转换的过程中边进行改名，并写入文件中去。

2.3各子程序流程图说明

2.3.1函数voidcreG（Graph&g,FILE*fpr）分析及流程图

在该函数中，读取文件中的信息，当打开文件不为空时，进行操作，先获取一整行的字符流，行数作为结点数；再重新到文件头，第1个花括号的字符为当前结点识别1能达到的结点，以此类推，读完文件构建图的边的信息。

其主要算法分析流程如图3所示。

图3函数voidcreG（Graph&g,FILE*fpr）流程图

2.3.2statechanging（states,intn,Graphg）分析流程图

该函数功能：

求当前状态集合的转移集合，即求s状态识别n之后的状态集合。

在这里，巧妙的用到了C++标准库STL中标准库Set集合。

从0状态，比如识别权重到达的下一状态都放在新的状态集合中。

其算法流程图如图4所示。

图4函数atechanging（states,intn,Graphg）分析流程图

2.3.3intequalSet（statem,staten）分析流程图

该函数功能用来判断两个状态集合是否相等，在NFA转DFA事时，需要标记其状态，直至没有新的状态集合出现。

若是想等的话，返回1；否则，返回0。

首先判断状态集合的长度（即里面元素的个数）是否相等；在此条件下再判断里面的元素是否一致。

其算法流程图如图5所示。

图5函数intequalSet（statem,staten）流程图

2.3.4voidinStates（state&s）分析流程图

判断当前状态是否在States数组中存在，若存在，进行改名；若不存在，改名后加入States数组。

初状态命名为A，利用上面的判断集合状态是否相等的函数来进行判断。

其算法思想如如6所示。

图6函数voidinStates（state&s）流程图

2.3.5voidNFATODFA（Graphg,FILE*fpw）分析流程图

该函数用来将NAF矩阵转换成DFA并命名，输出写在文件中。

其主要算法

流程如图7所示。

图7函数voidNFATODFA（Graphg,FILE*fpw）流程图

样例测试以及截图

样例测试1

从文件test.txt输入文件，输出结果保存在output.txt中，测试用例及输出结果如图8所示。

图8样例测试1测试结果

样例测试2

样例测试2的测试用例及输出结果如图9所示。

图9样例测试2测试结果

样例测试3

样例测试3的测试用例及输出结果如图10所示。

图10样例测试3测试结果

附录代码清单

#include

#include

#include

#include

#include

#include

usingnamespacestd;

#definemax50//定义结点最大数量

typedefcharvertype;//定义结点值域为字符类型

charb[1024];

intnum;//记录有穷字母表元素的个数

intlength;//记录States数组的长度

typedefstructarcnode//图的边信息

{

intadjvex;

intweight;//边所对应的权值（在这为到达下一状态所识别的数字）

structarcnode*next;

}arcnode;

typedefstructvnode//图的结点类型定义

{

vertypedata;

arcnode*next;

}vnode,adjlist[max];

typedefstruct//图的定义

{

adjlista;

intvexnum;

}Graph;

typedefstructstate

{

setSet;

charname;

}state;

stateStates[max];

intchange（Graphg,charc）//将图中结点转化为对应下标

{

inti;

for（i=0;i

{

if（c==g.a[i].data）

returni;

}

return-1;

}

voidcreG（Graph&g,FILE*fpr）

{

intcount=0;//构建图中的节点个数

while（!

feof（fpr））

{

fgets（b,1024,fpr）;//从文件中读取一行的字符串，放在b数组中

if（strlen（b）>1）//获取文件中图的结点个数

{

inti=0;

while（b[i]==''）

{

i++;

}

g.a[count].data=b[i];

g.a[count].next=NULL;

count++;

}

}

g.vexnum=count;

rewind（fpr）;//将文件指针返回到开头位置

count=0;

arcnode*s;

while（!

feof（fpr））//再次扫描文件将边的信息添上，构造图

{

intweight=0;//边所对应的权值,每一行权值都从0开始

fgets（b,1024,fpr）;

if（strlen（b）>1）

{

for（inti=0;i

{

if（b[i]=='{'）

{

weight++;

if（num

num=weight;

i++;

if（b[i]=='N'）

i=i+4;

while（b[i]!

='}'）

{

if（b[i]!

=','）

{

intx=change（g,b[i]）;

s=（arcnode*）malloc（sizeof（arcnode））;//临接表法构建图

s->adjvex=x;

s->weight=weight;

s->next=g.a[count].next;

g.a[count].next=s;

}

i++;

}

}

}

count++;

}

}

}

statechanging（states,intn,Graphg）//求当前状态集合的转移集合，即求s状态识别n之后的状态集合

{

statet;

arcnode*m;

set:

:

iteratoritr;//迭代器

for（itr=s.Set.begin（）;itr!

=s.Set.end（）;itr++）//遍历当前s状态中集合元素

{

inti=*itr;

m=g.a[i].next;

while（m）

{

if（m->weight==n）

{

t.Set.insert（m->adjvex）;//插入当前容器中

}

m=m->next;

}

}

returnt;

}

intequalSet（statem,staten）//比较两个状态的set集合内容是否相等

{

intflag=1;

if（m.Set.size（）!

=n.Set.size（））//首先集合长度的比较

{

flag=0;

returnflag;

}

set:

:

iteratoritrm;

set:

:

iteratoritrn;

for（itrm=m.Set.begin（）,itrn=n.Set.begin（）;itrm!

=m.Set.end（）;itrm++,itrn++）

{

intm=*itrm;

intn=*itrn;

if（m!

=n）

{

flag=0;

break;

}

}

returnflag;

}

voidinStates（state&s）//判断当前状态是否在States数组中存在，若存在，进行改名；若不存在，改名后加入States数组

{

intf=0;

if（length==0）

{

States[0]=s;

States[0].name='A';

length++;

}

else

{

for（inti=0;i

{

if（equalSet（States[i],s）==1）//若存在，进行改名

{

s.name=States[i].name;

f=1;

break;

}

}

if（f==0）//若不存在，改名后加入States数组

{

s.name=States[length-1].name+1;

States[length]=s;

length++;

}

}

}

voidNFATODFA（Graphg,FILE*fpw）

{

states,t;

s.Set.insert（0）;

s.name='A';

inStates（s）;

for（inti=0;i

{

cout<<"{";

fprintf（fpw,"{"）;

set:

:

iteratoritr;//set容器中迭代器，相当于一指针

for（itr=States[i].Set.begin（）;itr!

=States[i].Set.end（）;itr++）//遍历当前s状态中集合元素

{

if（States[i].Set.size（）==1）

{

inti=*itr;

cout<

fprintf（fpw,"%c",g.a[i].data）;

}

else

{

inti=*itr;

cout<

fprintf（fpw,"%c,",g.a[i].data）;

}

}

cout<<"}";

fprintf（fpw,"}"）;

cout<

fprintf（fpw,"%c",States[i].name）;

for（intj=1;j<=num;j++）

{

t=changing（States[i],j,g）;

inStates（t）;

cout<

fprintf（fpw,"%c",t.name）;

}

cout<

fprintf（fpw,"\n"）;

}

}

intmain（）

{

Graphg;

FILE*fpr=fopen（"G:

//test.txt","r"）;

FILE*fpw=fopen（"G:

//output.txt","w"）;

creG（g,fpr）;

NFATODFA（g,fpw）;

return0;

}