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

1、编译原理课程实践报告设计名称：NFA转化为DFA勺转换算法及实现二级学院：数学与计算机科学学院专业：计算机科学与技术班级：计科本091班姓名：林玉兰学号：0904402102指导老师：-梁徳塞日期：_2012 年6月摘要确定有限自动机确定的含义是在某种状态， 面临一个特定的符号只有一个转 换，进入唯一的一个状态。不确定的有限自动机则相反，在某种状态下，面临一 个特定的符号是存在不止一个转换，即是可以允许进入一个状态集合。在非确定的有限自动机NFA中，由于某些状态的转移需从若干个可能的后续 状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会

2、影响到FA的工作效率。而DFA则是确定的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必 要的。对于任意的一个不确定有限自动机(NFA都会存在一个等价的确定的有限 自动机(DFA，即L(N)=L(M)。本文主要是介绍如何将NFA转换为与之等价的简 化的DFA通过具体实例，结合图形，详细说明转换的算法原理。关键词：有限自动机；确定有限自动机(DFA，不确定有限自动机(NFAAbstractFinite automata is determinate and indeterminate two class. Determine the meaning is in a

3、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

4、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

5、 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 conver

6、t 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. 前言 ： 1.1背景1.2 实践目的 1.2 课程实践的意义 2. NF

7、A和DFA的概念 22.1 不确定有限自动机 NFA 22.2 确定有限自动机 DFA 33. 从NDF到DFA的等价变化步骤 53.1 转换思路 53.2. 消除空转移 53.3 子集构造法 74 程序实现 94.1 程序框架图 94.2 数据流程图 94.3 实现代码 104.4 运行环境 104.5 程序实现结果 105. 用户手册 126. 课程总结： 127. 参 考 文 献 128. 附录 131. 前言：A A1.1 背景有限自动机作为一种识别装置，它能准确地识别正规集，即识别正规文法所 定义的语言和正规式所表示的集合， 引入有穷自动机这个理论， 正是为词法分析 程序的自动构造寻

8、找特殊的方法和工具。有限自动机( Finite Automate )是用来模拟实物系统的数学模型，它包括 如下五个部分：? 有穷状态集 States? 输入字符集 Input symbols? 转移函数 Transitions? 起始状态 Start state? 接受状态 Accepting state(s)1.2 实践目的(1) 设计、编制、调式一个有穷自动机程序，加深对 NFA转换为DFA的原理 的理解。(2) 掌握NFA确定化的过程。1.2 课程实践的意义通过本课程设计教学所可以使我们充分理解和掌握 NFA DFA以及NFA确定 化过程的相关概念和知识， 理解和掌握子集法的相关知识和应

9、用， 编程实现对输 入NFA转换成DFA输出的功能。2. NFA 和 DFA 的概念2.1 不确定有限自动机 NFA即非确定有限自动机, 即自动机的每个结点所NFA(nondeterministic finite-state automata)个非确定的有限自动机NFA M是一个五元式：NFA M =(S, 2U , S , SO, F)其中S 有限状态集，2U 输入符号加上 射出的弧可以是工中一个字符或是& .SO 初态集F终态集转换函数 S X2 U 2S(2S -S的幕集一S的子集构成的集合)例 1 ： NFA M=(S,P,Z,O,1,f,s,p,z)其中f(s,O)=pf(z,O)=

10、pf(p,1)=zf(z,1)=pf(s,1)=s,zNFA的状态图表示如下：第2 页，共22页NFA矩阵表示:状态f字符01SPS,Z0PZ0ZPP12.2确定有限自动机DFADFA（deterministicfinite-stateautomata）即确定有限自动机，一个确定的有限自动机DFA M是一个五元式：M=（S, 艺，S , SO, Z）其中：S 有限状态集工一输入字母表S 映射函数（也称状态转换函数）S x艺SS (s,a)=S ,S, S S, a 艺S0初始状态S0 SZ终止状态集ZS例 2: DFAM=(S,U,V,Q,a,b,f,s,Q)其中f的定义为:f(S,a)=Uf

11、(S,b)=Vf(U,a)=Qf(U,b)=Vf(V,a)=Uf(V,b)=Qf(Q,a)=Qf(Q,b)=QDFA的状态图表示：假如DFAM含有m个状态，n个输入符，那么这个状态含有 m个节点，每个 节点最多有n个弧射出，整个图整个图含有唯一一个初态结点和若干个终态结 点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标以“ +”, 若f(ki ,a)=kj，则从状态结点ki到状结点kj画标记为a的弧：aaUSaVba,bDFA矩阵表示：一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。

12、用双箭头=标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0.宀状态、字符abSUV0UQV0VUQ0QQQ13. 从NDF到DFA的等价变化步骤事实已经证明了不管是非确定的有限自动机 M还是具有&-转移的非确定的 有限自动机，都可以找到一个与之等价的确定有限自动机，使得L( M =L(M)3.1转换思路由非确定的有限自动机出发构造与之等价的确定的有限自动机的办法是确 定的有限自动机的状态对应于非确定的有限自动机的状态集合，即要使转换后的DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入 一个输入符号后可能到达的所有状态，也就是说，在读入符号串a

13、1a2a3an之后，该DFA处在这样一个状态，该状态表示这个 NFA的状态的一个子集T,而T 是从NFA的开始状态沿着某个标记为a1a2a3an的路径可以到达的那些状态。3.2.消除空转移.消除N形式的产生式，即消除空转移。状态集合I的a弧转换la:定义为一状态集，是指从状态集I出发先经过a弧后再经过若干条&弧而能到达的状 态的集合。可以写作：la= &-closure(J) ，J=move(l,a),其中，J是从I中任 一状态出发经过一条a弧到达的状态集合，记为move(I,a)。s表示NFA的状态，T表示NFA的状态集合，a表示一个in put symbol -tra nsitio n（&

14、转换）就是说 in put symbol 为&时的 tran sitio n（转换）操作(operati on)描述(descripti on)-closure(s)从NFA的状态s出发，只通过 -transition到达的NFA的状态集合-closure(T)NFA的集合T中的状态p,只通过 -transition到达的NFA的状态集合，再求这些集合的交集。用数学表达就是p|p属于-closure（t） , t属于 Tmove(T,a)NFA的集合，这个集合在in put symbol为a,状态为T中任 意状态情况下，通过一个转换得到的集合例如：对于以下状态图中： -closure(0)=0

15、,1,2,4,7在这里设匸0,124,7，则因为有move(l,a)=3,8=J, 所以Ia= -closure(J)= -closure(3,8)=1,2,3,4,6,7,83.3子集构造法确定化每个多重转移，即拆分多值函数为单位函数，具体转换，采用子集构造法。以下面的基于字母表 工=a,b上的具有& -转移的非确定有限自动机 M为例。步骤1:以I , la、Ib等为列做表，其中I列第一行的内容是初态的& -闭包所得到的状态集合。并以此为I计算la、lb等，而 且在所计算出的la、lb等中 若有新的状态集产生，就重复以此新的集合为 l再此计算la、lb等，直到在所 得的la、lb等中不再产生

16、新的状态集为止。llalbx,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,115,1,325,1,43 o5,

17、1,325,1,3,2,6,y45,1,43 05,1,435,1,3 25,1,4,2,6,y55,1,3,2,6,y45,1,3,2,6,y45,1,4, 6,y65,1,4,2,6,y55,1,3, 6,y75,1,4,2,6,y55,1,4, 6,y65,1,3, 6,y75,1,4,2,6,y55,1,3, 6,y75,1,3,2,6,y45,1,4, 6,y6步骤3：画出转换后的DFA的状态图:第14页，共22页4.1程序框架图4.2数据流程图4程序实现NFA专化为NFA图结构NFA状态表DFA图结构初始化状态转换矩阵状 态 转 换 操 作4.3实现代码(见附录)4.4运行环境(1

18、) 开发平台：Microsoft visual C+6.0(2) 运行平台： Win dows xp/Wi ndows 20004.5程序实现结果实现NFA例题为：NFA M=(S,P,Z,0,1,f,s,p,z)其中f(s,O)=pf(z,O)=pf(P,1)=zf(z,1)=pf(s,1)=s,z根据例题输入NFA各边的信息得出结果如下图:5. 用户手册本程序应在Microsoft Visual C+ 6.0 下运行。NFA的确定化是编译过程 中一个重要的部分， 由于本程序的输入很多， 而且有多种格式的输入， 所以输入 时必须非常小心细致。 对于状态转换矩阵的表示， 冒号前的是新状态名，

19、冒号后 的是旧状态名。对于转化后的DFA表示，3个数据分别表示为起始状态、接受字 符和到达状态，例如（ 0,1,1 ）表示为新状态 0 接受字符 1 到达新字符状态 1。 运行结果因为转换字符输入顺序的不同， 得出的结果有可能与笔算得出的顺序有 所不同，但是结果依然是正确。6. 课程总结：通过这次课程实践设计， 让我对课堂上老师所讲到的不确定和确定有限自动 机有了更深的理解， 理解了它们的构造和怎样相互转化。 很好的理解了子集法的 演算过程。经过多次试验，在正确输入相关数据的情况下，程序能正常运行，当 错误操作或输入错误数据时，程序将应错误自动关闭。经过这次课程设计, 也让我深刻的认识到实践才

20、是最重要的。书本只能教给我们基础知识, 要怎样运用 ,将那些知识真正吸收 , 转化为自己的智慧 , 只有通过实践才能达到。 编译原理是一 门实用性很强，对我们的专业很有帮助的科目 , 我将会继续努力 , 不断增加自己的 知识面, 把编译原理学习的更好。同时我也发现自己对于有限自动机的知识掌握得还不是很多， 在这次课程实 践中，我懂得了怎样去和别人交流，更好地掌握和熟练了所学的知识。7. 参 考 文 献1）杨路明、郭浩志 .C 语言程序设计教程 .2003 年 12 月第 1版. 北京: 北京邮 电大学出版社 .20052）陈火旺.程序设计语言编译原理 .2000 年1月第 3版. 北京:国防工

21、业出版 社.2006.46-51（3）严蔚敏、吴伟民.数据结构（C语言版）.1997年4月第1版.北京：清华大 学出版社 .20054）王晓东编著 . 计算机算法设计与分析 . 电子工业出版社 .20048. 附录NFA转换为DFA采用C+编程实现代码如下 #include #include#define MAXS 100 using namespace std;string NODE; / 结点集合 string CHANGE; / 终结符集合 int N; /NFA 边数 struct edgestring first;string change;string last;struct ch

22、an string 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 &h

23、e,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 ;coutendlendl;for(i=0;ih;i+)c

24、out 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;coutvv请输入NFA各边信息，分别为：起点 条件空为* 终点，最后以#结束: endl;for(i=0;ibi.first;if(bi.first=#) break;cinbi.changebi.la

25、st;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 所输终态不在集合中，错误！

26、 endl; return; /coutendnode=endnodeendl; chan *t=new chanMAXS;t0.ltab=b0.first;h=1;eclouse(b0.first0,t0.ltab,b); / 求 /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); /for(k=0;klen;k+)/coutti.jihek;move(ti,k,b); /求 move(I,a)/coutti.jihekendl;

27、for(j=0;jti.jihek.length();j+) eclouse(ti.jihekj,ti.jihek,b); / for(j=0;jlen;j+)e-clouse求 e-clouse求 e-clousepaixu(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); / 输出状态转换矩阵 / 状

28、态重新命名 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); / 输出 DFA cout 其中终态为： endnodeendl; /DFA 最小化 m=2;sta.erase();flag=0;for(i=0;im;i