编译原理课程设计--NFA转化为DFA的转换算法及实现.doc

编译原理课程实践报告设计名称： NFA转化为DFA的转换算法及实现 二级学院： 数学与计算机科学学院 专 业： 计算机科学与技术 班 级： 计科本091班 姓 名： 林玉兰 学 号： 0904402102 指导老师： 梁德塞 日 期： 2012年6月 摘要确定有限自动机确定的含义是在某种状态，面临一个特定的符号只有一个转换，进入唯一的一个状态。不确定的有限自动机则相反，在某种状态下，面临一个特定的符号是存在不止一个转换，即是可以允许进入一个状态集合。在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会影响到FA的工作效率。而DFA则是确定的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必要的。对于任意的一个不确定有限自动机（NFA）都会存在一个等价的确定的有限自动机（DFA），即L(N)=L(M)。本文主要是介绍如何将NFA转换为与之等价的简化的DFA，通过具体实例，结合图形，详细说明转换的算法原理。关键词：有限自动机；确定有限自动机（DFA），不确定有限自动机（NFA） AbstractFinite automata is determinate and indeterminate two class. Determine the meaning is in a certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata is the opposite, in a certain state, faces a particular symbol is the presence of more than one conversion, that is to be allowed to enter a state set.Non deterministic finite state automata NFA, because of some state are transferred from a number of possible follow-up state are chosen, so a NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated, will undoubtedly affect the efficiency of the FA. While the DFA is determined, converting NFA to DFA will greatly improve the working efficiency, thus converting NFA to DFA is its necessary.For any a nondeterministic finite automaton ( NFA ) can be an equivalent deterministic finite automaton ( DFA ), L ( N ) =L ( M ). This paper mainly introduces how to convert NFA to equivalent simplified DFA, through concrete examples, combined with graphics, a detailed description of the algorithm principle of conversion.Keywords:：finite automata; deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA 目录1.前言：11.1背景11.2实践目的11.2课程实践的意义12.NFA和DFA的概念22.1 不确定有限自动机NFA22.2确定有限自动机DFA33从NDF到DFA的等价变化步骤53.1转换思路53.2.消除空转移53.3子集构造法74程序实现94.1程序框架图94.2 数据流程图94.3实现代码104.4运行环境104.5程序实现结果105.用户手册126.课程总结：127.参 考 文 献128. 附录131.前言：1.1背景有限自动机作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有限自动机（Finite Automate）是用来模拟实物系统的数学模型，它包括如下五个部分： 有穷状态集States 输入字符集Input symbols 转移函数Transitions 起始状态Start state 接受状态Accepting state(s) 1.2实践目的 （1）设计、编制、调式一个有穷自动机程序，加深对NFA转换为DFA的原理的理解。 （2）掌握NFA确定化的过程。1.2课程实践的意义通过本课程设计教学所可以使我们充分理解和掌握NFA，DFA以及NFA确定化过程的相关概念和知识，理解和掌握子集法的相关知识和应用，编程实现对输入NFA转换成DFA输出的功能。2.NFA和DFA的概念2.1 不确定有限自动机NFANFA(nondeterministic finite-state automata)即非确定有限自动机, 一个非确定的有限自动机NFA M是一个五元式: NFA M=(S, , , S0, F)其中 S有限状态集，输入符号加上,即自动机的每个结点所射出的弧可以是中一个字符或是. S0初态集 F终态集 转换函数 S 2S (2S -S的幂集S的子集构成的集合）例1： NFA M=(S,P,Z,0,1,f,s,p,z)其中f(s,0)=p f(z,0)=p f(p,1)=zf(z,1)=p f(s,1)=s,zNFA的状态图表示如下： SPZ10,1101NFA矩阵表示：状态 字符01SPS,Z0PZ0ZPP 12.2确定有限自动机DFADFA(deterministic finite-state automata)即确定有限自动机，一个确定的有限自动机DFA M是一个五元式: M=(S, ，, S0, Z) 其中: S 有限状态集 输入字母表 映射函数(也称状态转换函数) SS (s,a)=S , S, S S, a S0 初始状态 S0 S Z终止状态集 ZS例2：DFA M=(S,U,V,Q,a,b,f,s,Q) 其中f的定义为： f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q DFA的状态图表示：假如DFA M含有m个状态，n个输入符，那么这个状态含有m个节点，每个节点最多有n个弧射出，整个图整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标以“+”，若 f(ki ,a)=kj，则从状态结点ki到状结点kj画标记为a的弧：USVQabaaa,bbb DFA矩阵表示：一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头=标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0.状态 字符abSUV0 UQV0VUQ0QQQ13从NDF到DFA的等价变化步骤事实已经证明了不管是非确定的有限自动机M还是具有-转移的非确定的有限自动机，都可以找到一个与之等价的确定有限自动机，使得L（M）=L（M）。3.1转换思路由非确定的有限自动机出发构造与之等价的确定的有限自动机的办法是确定的有限自动机的状态对应于非确定的有限自动机的状态集合，即要使转换后的DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态，也就是说，在读入符号串a1a2a3an之后，该DFA处在这样一个状态，该状态表示这个NFA的状态的一个子集T，而T是从NFA的开始状态沿着某个标记为a1a2a3an的路径可以到达的那些状态。3.2.消除空转移.消除N形式的产生式，即消除空转移。状态集合I的a弧转换Ia:定义为一状态集，是指从状态集I出发先经过a弧后再经过若干条弧而能到达的状态的集合。可以写作： Ia= -closure(J)，J=move(I,a),其中，J是从I中任一状态出发经过一条a弧到达的状态集合，记为move(I,a)。s 表示NFA的状态，T 表示NFA的状态集合，a表示一个input symbol-transition(转换)就是说input symbol为时的transition(转换) 操作(operation)描述(description)-closure(s)从NFA的状态s出发，只通过-transition到达的NFA的状态集合-closure(T)NFA的集合T中的状态p，只通过-transition到达的NFA的状态集合，再求这些集合的交集。用数学表达就是 p|p 属于 -closure(t) , t属于Tmove(T,a)NFA的集合，这个集合在input symbol为a，状态为T中任意状态情况下，通过一个转换得到的集合例如：对于以下状态图中： -closure(0)=0,1,2,4,7在这里设I=0,1,2,4,7，则因为有move(I,a)=3,8=J,所以Ia= -closure(J)= -closure(3,8)=1,2,3,4,6,7,8012357689491003.3子集构造法确定化每个多重转移，即拆分多值函数为单位函数,具体转换，采用子集构造法。以下面的基于字母表=a,b上的具有-转移的非确定有限自动机M为例。X5346219Yabbaabab步骤1：以I，Ia、Ib等为列做表，其中I列第一行的内容是初态的- 闭包所得到的状态集合。并以此为I计算Ia、Ib等，而 且在所计算出的Ia、Ib等中若有新的状态集产生，就重复以此新的集合为I再此计算Ia、Ib等，直到在所得的Ia、Ib等中不再产生新的状态集为止。IIaIbx,5,15,1,35,1,45,1,35,1,3,2,6,y5,1,45,1,45,1,35,1,4,2,6,y5,1,3,2,6,y5,1,3,2,6,y5,1,4,6,y5,1,4,2,6,y5,1,3,6,y5,1,4,2,6,y5,1,4,6,y5,1,3,6,y5,1,4,2,6,y5,1,3,6,y5,1,3,2,6,y5,1,4,6,y步骤2：在上表中将原NFA初态的-闭包作为转换后的DFA的初态，包含原NFA终态的状态作为转换后的DFA的终态，并进行重新编号得到转换后的DFA的状态转移矩阵如下：abx,5,1 15,1,3 205,1,4 35,1,3 25,1,3,2,6,y405,1,4 35,1,4 35,1,3205,1,4,2,6,y 55,1,3,2,6,y 45,1,3,2,6,y415,1,4, 6,y 65,1,4,2,6,y 55,1,3, 6,y 7115,1,4,2,6,y 55,1,4, 6,y 65,1,3, 6,y 715,1,4,2,6,y 55,1,3, 6,y 75,1,3,2,6,y 45,1,4, 6,y 6步骤3：画出转换后的DFA的状态图：12376544567abbaaabbabaabb4程序实现4.1程序框架图NFA转化为DFANFA图结构NFA状态表DFA图结构初始化状态转换矩阵状态转换操作 4.2 数据流程图 开始NFA消除空转移子集构造法NFA状态矩阵DFA状态图4.3实现代码（见附录）4.4运行环境（1）开发平台：Microsoft visual C+6.0 （2）运行平台：Windows xp/Windows 20004.5程序实现结果实现NFA例题为：NFA M=(S,P,Z,0,1,f,s,p,z)其中f(s,0)=p f(z,0)=p f(p,1)=zf(z,1)=p f(s,1)=s,z根据例题输入NFA各边的信息得出结果如下图：5.用户手册本程序应在Microsoft Visual C+ 6.0下运行。NFA的确定化是编译过程中一个重要的部分，由于本程序的输入很多，而且有多种格式的输入，所以输入时必须非常小心细致。对于状态转换矩阵的表示，冒号前的是新状态名，冒号后的是旧状态名。对于转化后的DFA表示，3个数据分别表示为起始状态、接受字符和到达状态，例如（0,1,1）表示为新状态0接受字符1到达新字符状态1。运行结果因为转换字符输入顺序的不同，得出的结果有可能与笔算得出的顺序有所不同，但是结果依然是正确。6.课程总结：通过这次课程实践设计，让我对课堂上老师所讲到的不确定和确定有限自动机有了更深的理解，理解了它们的构造和怎样相互转化。很好的理解了子集法的演算过程。经过多次试验，在正确输入相关数据的情况下，程序能正常运行，当错误操作或输入错误数据时，程序将应错误自动关闭。经过这次课程设计,也让我深刻的认识到实践才是最重要的。书本只能教给我们基础知识,要怎样运用,将那些知识真正吸收,转化为自己的智慧,只有通过实践才能达到。编译原理是一门实用性很强，对我们的专业很有帮助的科目,我将会继续努力,不断增加自己的知识面,把编译原理学习的更好。同时我也发现自己对于有限自动机的知识掌握得还不是很多，在这次课程实践中，我懂得了怎样去和别人交流，更好地掌握和熟练了所学的知识。7.参 考 文 献（1）杨路明、郭浩志.C语言程序设计教程.2003年12月第1版. 北京:北京邮电大学出版社.2005（2）陈火旺.程序设计语言编译原理.2000年1月第3版. 北京:国防工业出版社.2006.46-51（3）严蔚敏、吴伟民.数据结构（C语言版）.1997年4月第1版.北京:清华大学出版社.2005（4）王晓东编著.计算机算法设计与分析.电子工业出版社.20048. 附录NFA转换为DFA采用C+编程实现代码如下#include#include#define MAXS 100using namespace std;string NODE; /结点集合string CHANGE; /终结符集合int N; /NFA边数struct edgestring first;string change;string last;struct chanstring ltab;string jiheMAXS;void kong(int a)int i;for(i=0;ia;i+) cout ;/排序void paixu(string &a)int i,j;char b;for(j=0;ja.length();j+) for(i=0;iNODE.find(ai+1) b=ai; ai=ai+1; ai+1=b; void eclouse(char c,string &he,edge b)int k;for(k=0;khe.length() he+=bk.last; eclouse(bk.last0,he,b); void move(chan &he,int m,edge b)int i,j,k,l;k=he.ltab.length();l=he.jihem.length();for(i=0;ik;i+) for(j=0;jhe.jihem.length() he.jihem+=bj.last0; for(i=0;il;i+) for(j=0;jhe.jihem.length() he.jihem+=bj.last0;/输出void outputfa(int len,int h,chan *t)int i,j,m;cout I ;for(i=0;ilen;i+) coutICHANGEi ;coutendl-endl;for(i=0;ih;i+) cout ti.ltab; m=ti.ltab.length(); for(j=0;jlen;j+) kong(8-m); m=ti.jihej.length(); coutti.jihej; coutendl;void main()edge *b=new edgeMAXS;int i,j,k,m,n,h,x,y,len;bool flag;string jhMAXS,endnode,ednode,sta;cout请输入NFA各边信息,分别为 ：起点 条件空为* 终点，最后以#结束：endl;for(i=0;ibi.first; if(bi.first=#) break; cinbi.changebi.last;N=i;/*for(j=0;jN;j+) coutbj.firstbj.changebj.lastendl;*/for(i=0;iNODE.length() NODE+=bi.first; if(NODE.find(bi.last)NODE.length() NODE+=bi.last; if(CHANGE.find(bi.change)CHANGE.length()&(bi.change!=*) CHANGE+=bi.change;len=CHANGE.length();cout结点中属于终态的是：endnode;for(i=0;iNODE.length() cout所输终态不在集合中，错误！endl; return; /coutendnode=endnodeendl;chan *t=new chanMAXS; t0.ltab=b0.first;h=1;eclouse(b0.first0,t0.ltab,b); /求e-clouse/coutt0.ltabendl;for(i=0;ih;i+) for(j=0;jti.ltab.length();j+) for(m=0;mlen;m+) eclouse(ti.ltabj,ti.jihem,b); /求e-clouse for(k=0;klen;k+) /coutti.jihek; move(ti,k,b); /求move(I,a) /coutti.jihekendl; for(j=0;jti.jihek.length();j+) eclouse(ti.jihekj,ti.jihek,b); /求e-clouse for(j=0;jlen;j+) paixu(ti.jihej); /对集合排序以便比较 for(k=0;kh;k+) flag=operator=(tk.ltab,ti.jihej); if(flag) break; if(!flag&ti.jihej.length() th+.ltab=ti.jihej; coutendl状态转换矩阵如下：endl;outputfa(len,h,t); /输出状态转换矩阵/状态重新命名string *d=new stringh;NODE.erase();coutendl重命名：endl;for(i=0;ih;i+) sta=ti.ltab; ti.ltab.erase(); ti.ltab=A+i; NODE+=ti.ltab; coutsta=ti.ltabendl; for(j=0;jendnode.length();j+) if(sta.find(endnodej)sta.length() d1=ednode+=ti.ltab; for(k=0;kh;k+) for(m=0;mlen;m+) if(sta=tk.jihem) tk.jihem=ti.ltab;for(i=0;iednode.length() d0+=NODEi;endnode=ednode;coutendlDFA如下：endl;outputfa(len,h,t); /输出DFAcout其中终态为：endnodeendl;/DFA最小化m=2;sta.erase();flag=0; for(i=0;im;i+) /coutdi=diendl; for