NFA转DFA.docx

1、NFA转DFA编译方法 实 验 报 告实验名称：子集构造法实现NFA的确定化实验要求1.功能：利用子集构造法实现NFA到DFA的转换2.输入NFANFA输入格式参见图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.确定各个子程序的功能并画出

2、流程图 5.设计子集构造算法 6.编码实现NFA确定化程序采用文本输入和输出的方式。程序从名为“test.txt”的文件中读入代表NFA状态的数据，将确定化后的结果保存到“output.txt”中。7.设计3-5个NFA测试实例，检验程序能否输出正确的DFA。8.报告内容包括：子集构造算法，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等子集构造法NFA确定化的算法思想1.1 NFA的确定化（子集构造法）即将NFA M=（S，f，Z ） DFA =（，）.初始时, -closure(S0) 是state中唯一的状态且未被标记;.whi

3、le states中存在一个未标记的状态T do begin标记T; for 每个输入符号 a do beginU := -closure ( move (T, a) );if U 没在state中 then将U作为一个未被标记的状态添加到statef T, a := Uendend 将含有NFA终态的子集加入中 重新命名S和Z 中的状态，整理f。1.2 NFA转DFA实现 这里，为直观显示上面所述算法的而实现，可直观看图1所示的NFA状态转化图，其等价的DFA状态转化图如图2所示。 图1 NFA状态转换图与之等价的DFA如图2：图2 DFA状态转换图书上所示例子的状态标的转换如图3所示，简单

4、明了，开始由S未标记的状态开始，根据子集构造法实现NFA确定化为DFA。详细设计说明2.1主要用到的数据结构定义 在NFA中，采取用图的结构在存储转换信息，用数字标记转换状态的以及记录状态的个数（即图中结点的个数），边的权值（用来表示当前状态识别的字符到达下一状态）为方便起见，用数字标记。typedef struct arcnode /图的边信息int adjvex; int weight; /边所对应的权值（在这为到达下一状态所识别的数字）struct arcnode *next;arcnode;typedef struct vnode /图的结点类型定义 vertype data; arc

5、node *next;vnode,adjlistmax;typedef struct /图的定义 adjlist a; int vexnum;Graph;2.2主要函数的说明int change(Graph g,char c)：将图中结点转化为对应下标(0,1,2,3.)void creG(Graph &g,FILE *fpr)：从文件中读取信息，将信息转换成图的存储形式state changing(state s,int n,Graph g)：求当前状态集合的转移集合，即求s状态识别n之后的状态集合int equalSet(state m,state n)：比较两个状态的set集合内容是否相

6、等，若相等，返回数字1，否则，返回数字0。oid inStates(state &s)：判断当前状态是否在States数组中存在，若存在，进行改名；若不存在，改名后加入States数组void NFATODFA(Graph g,FILE *fpw)：NFA转DFA，在变转换的过程中边进行改名，并写入文件中去。2.3各子程序流程图说明2.3.1 函数void creG(Graph &g,FILE *fpr)分析及流程图 在该函数中，读取文件中的信息，当打开文件不为空时，进行操作，先获取一整行的字符流，行数作为结点数；再重新到文件头，第1个花括号的字符为当前结点识别1能达到的结点，以此类推，读完文

7、件构建图的边的信息。其主要算法分析流程如图3所示。 图3 函数 void creG(Graph &g,FILE *fpr)流程图2.3.2 state changing(state s,int n,Graph g)分析流程图 该函数功能：求当前状态集合的转移集合，即求s状态识别n之后的状态集合。在这里，巧妙的用到了C+标准库STL中标准库Set集合。从0状态，比如识别权重到达的下一状态都放在新的状态集合中。其算法流程图如图4所示。 图4 函数ate changing(state s,int n,Graph g)分析流程图2.3.3 int equalSet(state m,state n)分析

8、流程图 该函数功能用来判断两个状态集合是否相等，在NFA转DFA事时，需要标记其状态，直至没有新的状态集合出现。若是想等的话，返回1；否则，返回0。首先判断状态集合的长度（即里面元素的个数）是否相等；在此条件下再判断里面的元素是否一致。其算法流程图如图5所示。 图5 函数int equalSet(state m,state n)流程图2.3.4 void inStates(state &s)分析流程图判断当前状态是否在States数组中存在，若存在，进行改名；若不存在，改名后加入States数组。初状态命名为A，利用上面的判断集合状态是否相等的函数来进行判断。其算法思想如如6所示。 图6 函数

9、void inStates(state &s)流程图2.3.5 void NFATODFA(Graph g,FILE *fpw)分析流程图该函数用来将NAF矩阵转换成DFA并命名，输出写在文件中。其主要算法流程如图7所示。 图7函数void NFATODFA(Graph g,FILE *fpw)流程图样例测试以及截图样例测试1 从文件test.txt输入文件，输出结果保存在output.txt中，测试用例及输出结果如图8所示。 图8样例测试1测试结果样例测试2样例测试2的测试用例及输出结果如图9所示。 图9样例测试2测试结果样例测试3样例测试3的测试用例及输出结果如图10所示。图10样例测试3

10、测试结果 附录代码清单 #include#include#include #include #include #includeusing namespace std;#define max 50 /定义结点最大数量typedef char vertype; /定义结点值域为字符类型char b1024;int num; /记录有穷字母表元素的个数int length; /记录States数组的长度typedef struct arcnode /图的边信息 int adjvex; int weight; /边所对应的权值（在这为到达下一状态所识别的数字） struct arcnode *next

11、;arcnode;typedef struct vnode /图的结点类型定义 vertype data; arcnode *next;vnode,adjlistmax;typedef struct /图的定义 adjlist a; int vexnum;Graph;typedef struct state set Set; char name;state;state Statesmax;int change(Graph g,char c) /将图中结点转化为对应下标 int i; for(i=0;i1) /获取文件中图的结点个数 int i = 0; while(bi= ) i+; g.ac

12、ount.data=bi; g.acount.next=NULL; count+; g.vexnum=count; rewind(fpr); /将文件指针返回到开头位置 count = 0; arcnode *s; while(!feof(fpr) /再次扫描文件将边的信息添上，构造图 int weight=0; /边所对应的权值,每一行权值都从0开始 fgets(b,1024,fpr); if(strlen(b)1) for(int i=0;istrlen(b)-1;i+) if(bi=) weight+; if(numadjvex=x; s-weight=weight; s-next=g.

13、acount.next; g.acount.next=s; i+; count+; state changing(state s,int n,Graph g)/求当前状态集合的转移集合，即求s状态识别n之后的状态集合 state t; arcnode *m; set:iterator itr; /迭代器 for(itr = s.Set.begin();itr!=s.Set.end();itr+)/遍历当前s状态中集合元素 int i = *itr; m = g.ai.next; while(m) if(m-weight=n) t.Set.insert(m-adjvex); /插入当前容器中 m

14、=m-next; return t;int equalSet(state m,state n)/比较两个状态的set集合内容是否相等 int flag = 1; if(m.Set.size()!=n.Set.size() /首先集合长度的比较 flag = 0; return flag; set:iterator itrm; set:iterator itrn; for(itrm = m.Set.begin(),itrn = n.Set.begin();itrm!=m.Set.end();itrm+,itrn+) int m = *itrm; int n = *itrn; if(m!=n) f

15、lag = 0; break; return flag;void inStates(state &s)/判断当前状态是否在States数组中存在，若存在，进行改名；若不存在，改名后加入States数组 int f = 0; if(length=0) States0=s; States0.name=A; length+; else for(int i=0;ilength;i+) if(equalSet(Statesi,s)=1)/若存在，进行改名 s.name=Statesi.name; f = 1; break; if(f = 0)/若不存在，改名后加入States数组 s.name=Stat

16、eslength-1.name+1; Stateslength=s; length+; void NFATODFA(Graph g,FILE *fpw) state s,t; s.Set.insert(0); s.name=A; inStates(s); for(int i=0;ilength;i+) cout; fprintf(fpw,); set:iterator itr; /set容器中迭代器，相当于一指针 for(itr = Statesi.Set.begin();itr!=Statesi.Set.end();itr+)/遍历当前s状态中集合元素 if(Statesi.Set.size

17、()=1) int i = *itr; coutg.ai.data; fprintf(fpw,%c,g.ai.data); else int i = *itr; coutg.ai.data,; fprintf(fpw,%c,g.ai.data); cout; fprintf(fpw,); coutStatesi.name; fprintf(fpw,%c,Statesi.name); for(int j=1;j=num;j+) t = changing(Statesi,j,g); inStates(t); coutt.name; fprintf(fpw,%c,t.name); coutendl; fprintf(fpw,n); int main() Graph g; FILE *fpr = fopen(G:/test.txt,r); FILE *fpw = fopen(G:/output.txt,w); creG(g,fpr); NFATODFA(g,fpw); return 0;