编译原理报告：NFA转DFA(详解,附源代码)

编译原理实习报告

学号：******

班级：******

姓名：******

日期：2015

目录

1.题目及需求分析 (3)

2.设计分析 (3)

3.调试分析 (7)

4.用户手册 (7)

5.测试结果 (7)

6.总结 (7)

7.源代码 (8)

题目：NFA转换为等价的DFA

实习时间：【问题描述】以定理“设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的

确定的有穷自动机”为理论基础，设计算法实现将不确定的有穷自动机(NFA)转换为与之等价的确定的有穷自动机(DFA)。

【基本要求】

①确定能够表示FA的合适的结构，以便FA的输入和输出

②设计的算法既要成功实现题目要求的功能，又要高效、鲁棒

③程序中的函数、变量等命名要规则，可读性要强(易懂)

1．需求分析

(1) 要将以状态转换图表示的NFA转换为DFA，首先应设计一个结构来表示FA，以便图形式的FA便于输入和输出。

(2) 设计合适的算法来实现NFA的确定化，这里用子集法来构造等价的DFA。

(3) 测试数据:课本P59例

转换前的NFA 转换后的DFA 2．设计

（1）数据结构设计

由于FA是一个图，可想到用图的存储结构来存储FA，但是，FA中两个结点之间的路径可以不只一条，这让想考虑用邻接矩阵来存储的FA处理起来有点复杂，我采用的是“结点-边-结点”

式的三元组来表示FA。FA有多少条边就应该有多少个这样的三元组，以一个数组来存放这些三元组，那么一个FA就可以表示出来了。

此外，由子集法的步骤可见，集合(set)这一结构应该使用，，set结构符合我们数学的集合要求，不含相同元素，并且两个集合间还可以进行比较是否相等，十分有利于我们的程序实现。

表示FA的结构：

//Triad(三元组)：S →aB即

（S,a,B）

struct Triad{

char start;

集合与栈使用库里面的标准集合、栈。即包含头文件set、stack

（2）文件结构

程序不是很复杂，加之使用到的数据结构是标准库里的，文件只有一个，其中有#include和#include。

（3）程序基本框架概览

struct Triad{ }; // FA的基本组成

结构

int main(){

初始化工作；

determined(); //确定化

（4）主要函数的实现

伪代码具有简明扼要的特点，利用伪代码子来表示程序流程有利于理解和后续实现。

子集法伪代码：

此外，求ε的传递闭包要利用栈这一数据结构做辅助，其伪代码如下：

再在伪代码的基础上来编写这些核心函数就方便多了，具体代码如下：

3．调试分析

优点分析：NFA的输入只要求输入边的条数即可开始输入组成FA的基本结构(即三元组)，而有多少引起状态转换的输入都交给程序自己去完成，这一点就显得很简洁，对于用户来说也便捷！

缺点分析：没有可视化，整个程序的输入输出是通过控制台完成的。

解决办法：可合适的使用MFC可视化编程完成(这个有余力可以考虑一下)。

4．用户手册

该程序的使用十分简单，直接按要求输入相应数据就是。

5．测试数据及测试结果

课本P59例：

6．总结

优点通过这次的实习，对编译原理NFA、DFA及之间的等价转换有了更加深刻的理解，也学会了利用伪代码来设计程序，由框架到细节的实现，这种设计相当便利高效。团队成员之间交流思想取长补短也让我学到了好多思想和方法。

7.源代码

#include

#include

#include

using namespace std;

tart>>G[i].edge>>G[i].end;

v1.0 可编辑可修改}

set Edge;

for(int j=0; j

(G[j].edge);

}

int n=();

char* input=new char[n];

set::iterator it;

j=0;

for (it = (); it != (); it++){

input[j]=*it;

j++;

}

determined(G, N, input, n);

return 0;

}

set e_closure(set T, Triad G[], int N)

{

set U = T;

stack S;

set::iterator it;

for (it = (); it != (); it++)

(*it);

char t;

while (!())

{

t = ();

();

for (int i=0;i

{

if (G[i].start== t && G[i].edge=='*')

{

(G[i].end);

(G[i].end);

}

}

}

return U;

}

set move(set I, char a, Triad G[], int N){ set U;

set::iterator it;

for (it = (); it != (); it++)

for(int i=0; i

if (G[i].start== *it && G[i].edge==a)

(G[i].end);

}

return U;

}

void determined(Triad G[], int N, char* input, int n){

cout<

bool marked[MAX_NODES];

for(int i=0; i

marked[i]=false;

set C[MAX_NODES];

char s0=G[0].start;

set T0,T1;

(s0);

T1=e_closure(T0, G, N);

C[0]=T1;

i=0;

while(!C[i].empty() && marked[i]==false && i

marked[i]=true;

egin(); it != C[i].end(); it++)

cout<<*it<<",";

cout<

*/

for(int j=0; j

if(input[j] != '*'){

set U=e_closure(move(C[i], input[j], G, N), G, N);

if(!()) {

bool inC=false;

int k=0;

while(!C[k].empty() && k

if(U==C[k]){

inC=true;

break;

}

k++;

}

if(!inC){

k=0;

while(!C[k].empty() && k

k++;

}

C[k]=U;

}

cout<

}

}

}

i++;

}

mpty()){

bool is_final_state=false;

set::iterator it;

for (it = C[i].begin(); it != C[i].end(); it++){ if(*it == '#'){

is_final_state=true;

break;

}

}

if(is_final_state) cout<

i++;

}

cout<

}