编译原理课程设计

编译原理课程实践报告设计名称：NFA转化为DFA的转换算法及实现二级学院：数学与计算机科学学院专业：计算机科学与技术班级：计科本091班名：学号：指导老师：日期：2012年6月摘要确定有限自动机确定的含义是在某种状态，面临一个特定的符号只有一个转换，进入唯一的一个状态。不确定的有限自动机则相反，在某种状态下，面临一个特定的符号是存在不止一个转换，即是可以允许进入一个状态集合。在非确定的有限自动机NFA中，由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会影响到FA的工作效率。而DFA则是确定的，将NFA转化为DFA将大大提高工作效率，因此将NFA转化为DFA是有其一定必要的。对于任意的一个不确定有限自动机（NFA）都会存在一个等价的确定的有限自动机（DFA），即L（N）=L（M）。本文主要是介绍如何将NFA转换为与之等价的简化的DFA，通过具体实例，结合图形，详细说明转换的算法原理。关键词：有限自动机；确定有限自动机（DFA），不确定有限自动机（NFA）AbstractFiniteautomataisdeterminateandindeterminatetwoclass.Determinethemeaningisinacertainstate,facesaparticularsymbolonlyoneconversion,enteronlyonestate.Notdeterministicfiniteautomataistheopposite,inacertainstate,facesaparticularsymbolisthepresenceofmorethanoneconversion,thatistobeallowedtoenterastateset.NondeterministicfinitestateautomataNFA,becauseofsomestatearetransferredfromanumberofpossiblefollow-upstatearechosen,soaNFAsymbolstringrecognitionmustbeatrialprocess.Thisuncertaintytotherecognitionprocessbroughtaboutbyrepeated,willundoubtedlyaffecttheefficiencyoftheFA.WhiletheDFAisdetermined,convertingNFAtoDFAwillgreatlyimprovetheworkingefficiency,thusconvertingNFAtoDFAisitsnecessary.Foranyanondeterministicfiniteautomaton(NFA)canbeanequivalentdeterministicfiniteautomaton(DFA),L(N)=L(M).ThispapermainlyintroduceshowtoconvertNFAtoequivalentsimplifiedDFA,throughconcreteexamples,combinedwithgraphics,adetaileddescriptionofthealgorithmprincipleofconversion.Keywords::finiteautomata;deterministicfiniteautomaton(DFA),nondeterministicfiniteautomaton(NFA目录TOC\o"1-5"\h\z\o"CurrentDocument"前言：1\o"CurrentDocument"1.1背景11.2实践目的1\o"CurrentDocument"1.2课程实践的意义1\o"CurrentDocument"NFA和DFA的概念22.1不确定有限自动机NFA22.2确定有限自动机DFA3\o"CurrentDocument"3.从NDF到DFA的等价变化步骤53.1转换思路53.2.消除空转移53.3子集构造法7\o"CurrentDocument"4程序实现94.1程序框架图94.2数据流程图94.3实现代码104.4运行环境10\o"CurrentDocument"4.5程序实现结果10\o"CurrentDocument"用户手册12\o"CurrentDocument"课程总结：12\o"CurrentDocument"参考文献12\o"CurrentDocument"附录131.前言:1.1背景有限自动机作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有限自动机(FiniteAutomate)是用来模拟实物系统的数学模型，它包括如下五个部分：•有穷状态集States输入字符集Inputsymbols转移函数Transitions起始状态Startstate接受状态Acceptingstate(s)1.2实践目的设计、编制、调式一个有穷自动机程序，加深对NFA转换为DFA的原理的理解。掌握NFA确定化的过程。1.2课程实践的意义通过本课程设计教学所可以使我们充分理解和掌握NFA，DFA以及NFA确定化过程的相关概念和知识，理解和掌握子集法的相关知识和应用，编程实现对输入NFA转换成DFA输出的功能。2.NFA和DFA的概念2.1不确定有限自动机NFANFA(nondeterministicfinite-stateautomata)即非确定有限自动机，一个非确定的有限自动机NFAM’是一个五元式：NFAM’=(S,SU{e),5,S0,F)其中S一有限状态集，SU{E}一输入符号加上8,即自动机的每个结点所射出的弧可以是习中一个字符或是8.S0—初态集F一终态集5—转换函数SX2U{8}-2S(2S--S的幕集一S的子集构成的集合)例1：NFAM=({S,P,Z},{0,1},f,{s,p},{z})其中f(s,0)={p}f(z,0)={p}f(p,1)={z}f(z,1)={p}f(s,1)={s,z}①NFA的状态图表示如下：②NFA矩阵表示:状态'滓符0状态'滓符0SPP{}ZP1S,Z0Z0P12.2确定有限自动机DFADFA(deterministicfinite-stateautomata)即确定有限自动机，一个确定的有限自动机DFAM是一个五元式：M=(S,S,5,S0,Z)其中:S—有限状态集习一输入字母表5一映射函数(也称状态转换函数)SX一S5(s,a)=S’，S,S’eS,a^ES0一初始状态SOeSZ一终止状态集ZS例2：DFAM=({S,U,V,Q},{a,b},f,s,{Q})其中f的定义为：f(S,a)=Uf(S,b)=Vf(U,a)=Qf(U,b)=Vf(V,a)=Uf(V,b)=Qf(Q,a)=Qf(Q,b)=Q①DFA的状态图表示：假如DFAM含有m个状态，n个输入符，那么这个状态含有m个节点，每个节点最多有n个孤射出，整个图整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“二＞”或标以“-”，终态结点用双圈表示或标以“+”，若f(ki,a)=kj，则从状态结点ki到状结点kj画标记为a的孤：②DFA矩阵表示：一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头二＞标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0.

状M，字符aSUUQVUQQbV0状M，字符aSUUQVUQQbV0V0Q0Q1事实已经证明了不管是非确定的有限自动机M还是具有8-转移的非确定的有限自动机，都可以找到一个与之等价的确定有限自动机，使得L(M)=L(M’)。3.1转换思路由非确定的有限自动机出发构造与之等价的确定的有限自动机的办法是确定的有限自动机的状态对应于非确定的有限自动机的状态集合，即要使转换后的DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态，也就是说，在读入符号串a1a2a3・・・an之后，该DFA处在这样一个状态，该状态表示这个NFA的状态的一个子集T，而T是从NFA的开始状态沿着某个标记为a1a2a3・・・an的路径可以到达的那些状态。3.2.消除空转移.消除N形式的产生式，即消除空转移。状态集合I的a孤转换Ia:定义为一状态集，是指从状态集I出发先经过a孤后再经过若干条8孤而能到达的状态的集合。可以写作：Ia=e-closure(J)，J=move(I,a)，其中，J是从I中任一状态出发经过一条a孤到达的状态集合，记为move(I,a)。

s表示NFA的状态，T表示NFA的状态集合，a表示一个inputsymbole-transition（e转换）就是说inputsymbol为e时的transition（转换）操作(operation)描述(description)e-closure(s)从NFA的状态s出发，只通过e-transition到达的NFA的状态集合e-closure(T)NFA的集合T中的状态p，只通过e-transition到达的NFA的状态集合，再求这些集合的交集。用数学表达就是（p|p属于e-closure（t）,t属于T}||move(T,a)NFA的集合，这个集合在inputsymbol为a，状态为T中任意状态情况下，通过一个转换得到的集合例如：对于以下状态图中：e-closure({0})={0,1,2,4,7}在这里设I={0,1,2,4,7}，则因为有move(I,a)={3,8}=J,所以Ia=e-closure(J)=e-closure({3,8})={1,2,3,4,6,7,8}e

3.3子集构造法确定化每个多重转移，即拆分多值函数为单位函数，具体转换，采用子集构造法。以下面的基于字母表£={a,b}上的具有^-转移的非确定有限自动机M为例。步骤1：以I,Ia、Ib等为列做表，其中I列第一行的内容是初态的8-闭包所得到的状态集合。并以此为I计算Ia、Ib等，而且在所计算出的Ia、Ib等中若有新的状态集产生，就重复以此新的集合为I再此计算Ia、Ib等，直到在所得的Ia、Ib等中不再产生新的状态集为止。IIaIb{x,5,1}{5,1,3}{5,1,4}{5,1,3}{5,1,3,2,6,y}{5,1,4}{5,1,4}{5,1,3}{5,1,4,2,6,y}{5,1,3,2,6,y}{5,1,3,2,6,y}{5,1,4,6,y}{5,1,4,2,6,y}{5,1,3,6,y}{5,1,4,2,6,y}{5,1,4,6,y}{5,1,3,6,y}{5,1,4,2,6,y}{5,1,3,6,y}{5,1,3,2,6,y}{5,1,4,6,y}

步骤2：在上表中将原NFA初态的e-闭包作为转换后的DFA的初态，包含原NFA终态的状态作为转换后的DFA的终态，并进行重新编号得到转换后的DFA的状态转移矩阵如下：ab{x,5,1}1{5,1,3}2{5,1,4}30{5,1,3}2{5,1,3,2,6,y}4{5,1,4}30{5,1,4}3{5,1,3}2{5,1,4,2,6,y}0{5,1,3,2,6,y}4{5,1,3,2,6,y}4{5,1,4,6,y}6{5,1,4,2,6,y}5{5,1,3,6,y}7{5,1,4,2,6,y}15{5,1,4,6,y}6{5,1,3,6,y}7{5,1,4,2,6,y}15{5,1,3,6,y}7{5,1,3,2,6,y}4{5,1,4,6,y}6步骤3：画出转换后的DFA的状态图:b4.1程序框架图4.2数据流程图4程序实现NFA转化为N

F

A

图

结

构NFA状态表4.3实现代码（见附录）4.4运行环境开发平台：MicrosoftvisualC++6.0运行平台：Windowsxp/Windows20004.5程序实现结果实现NFA例题为：NFAM=({S,P,Z},{0,1},f,{s,p},{z})

其中f(z,0)={p}f(s,1)=f(z,0)={p}f(s,1)={s,z}f(p,1)={z}f(z,1)={p}根据例题输入NFA各边的信息得出结果如下图:情输入NFH各边信息-分别为：起点条件［空为刁终点，最后以K结束：S0pB0pH)12QlpE1Ssis结点中属于终态的-2曰状态转换矩阵如下■I10II——SVS2V2szpspz2VPspzpspzM命名:<s>=Akp>=BksE>=cSpH>=E疏如下:IISII——ABcEDCBEDBBEB柱中终态为:CDEE集合划分:3)<CE^<B><»>屋命名:<A>=A<CE>=B<BJ=Cp>=D屈小化D®如下：IIQII——ACBBCBCDDCC用户手册本程序应在MicrosoftVisualC++6.0下运行。NFA的确定化是编译过程中一个重要的部分，由于本程序的输入很多，而且有多种格式的输入，所以输入时必须非常小心细致。对于状态转换矩阵的表示，冒号前的是新状态名，冒号后的是旧状态名。对于转化后的DFA表示，3个数据分别表示为起始状态、接受字符和到达状态，例如（0,1,1）表示为新状态0接受字符1到达新字符状态1。运行结果因为转换字符输入顺序的不同，得出的结果有可能与笔算得出的顺序有所不同，但是结果依然是正确。课程总结:通过这次课程实践设计，让我对课堂上老师所讲到的不确定和确定有限自动机有了更深的理解，理解了它们的构造和怎样相互转化。很好的理解了子集法的演算过程。经过多次试验，在正确输入相关数据的情况下，程序能正常运行，当错误操作或输入错误数据时，程序将应错误自动关闭。经过这次课程设计，也让我深刻的认识到实践才是最重要的。书本只能教给我们基础知识，要怎样运用，将那些知识真正吸收，转化为自己的智慧，只有通过实践才能达到。编译原理是一门实用性很强，对我们的专业很有帮助的科目，我将会继续努力，不断增加自己的知识面，把编译原理学习的更好。同时我也发现自己对于有限自动机的知识掌握得还不是很多，在这次课程实践中，我懂得了怎样去和别人交流，更好地掌握和熟练了所学的知识。参考文献（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<iostream>#include<string>#defineMAXS100usingnamespacestd;stringNODE;//结点集合stringCHANGE;//终结符集合intN;//NFA边数structedge(stringfirst;stringchange;stringlast;};structchan(stringltab;stringjihe[MAXS];};voidkong(inta)(inti;for(i=0;i<a;i++)cout<<'';}〃排序voidpaixu(string&a)(inti,j;charb;for(j=0;j<a.length();j++)for(i=0;i<a.length();i++)if(NODE.find(a[i])>NODE.find(a[i+1]))(b=a[i];a[i]=a[i+1];a[i+1]=b;}}voideclouse(charc,string&he,edgeb[])(intk;for(k=0;k<N;k++)(if(c==b[k].first[0])if(b[k].change=二〃*〃)(if(he.find(b[k].last)>he.length())he+=b[k].last;eclouse(b[k].last[0],he,b);}}}voidmove(chan&he,intm,edgeb[])(inti,j,k,l;k=he.ltab.length();l二he.jihe[m].length();for(i=0;i<k;i++)for(j=0;j<N;j++)if((CHANGE[m]==b[j].change[0])&&(he.ltab[i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())he.jihe[m]+=b[j].last[0];for(i=0;i<l;i++)for(j=0;j<N;j++)if((CHANGE[m]==b[j].change[0])&&(he.jihe[m][i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())he.jihe[m]+=b[j].last[0];}〃输出voidoutputfa(intlen,inth,chan*t)(inti,j,m;cout<<"I";for(i=0;i<len;i++)cout<<'I'<<CHANGE[i]<<〃";cout<<endl<<""<<endl;for(i=0;i<h;i++)(cout<<''<<t[i].ltab;m=t[i].ltab.length();for(j=0;j<len;j++)(kong(8-m);m=t[i].jihe[j].length();cout<<t[i].jihe[j];}cout<<endl;}}voidmain()(edge*b=newedge[MAXS];inti,j,k,m,n,h,x,y,len;boolflag;stringjh[MAXS],endnode,ednode,sta;cout<<"请输入NFA各边信息,分别为：起点条件[空为*]终点，最后以#结束:"<<endl;for(i=0;i<MAXS;i++)(cin>>b[i].first;if(b[i].first==〃#〃)break;cin>>b[i].change>>b[i].last;}N=i;/*for(j=0;j<N;j++)cout<<b[j].first<<b[j].change<<b[j].last<<endl;*/for(i=0;i<N;i++)(if(NODE.find(b[i].first)>NODE.length())NODE+=b[i].first;if(NODE.find(b[i].last)>NODE.length())NODE+=b[i].last;if((CHANGE.find(b[i].change)>CHANGE.length())&&(b[i].change!二〃*〃))CHANGE+=b[i].change;}len=CHANGE.length();cout<<〃结点中属于终态的是：〃<<endl;

cin>>endnode;for(i=0;i<endnode.length();i++)if(NODE.find(endnode[i])>NODE.length())(cout<<"所输终态不在集合中，错误！"<<endl;return;}//cout<<"endnode="<<endnode<<endl;chan*t=newchan[MAXS];t[0].ltab=b[0].first;h=1;eclouse(b[0].first[0],t[0].ltab,b);//求e-clouse//cout<<t[0].ltab<<endl;for(i=0;i<h;i++)(for(j=0;j<t[i].ltab.length();j++)for(m=0;m<len;m++)eclouse(t[i].ltab[j],t[i].jihe[m],b);//求e-clousefor(k=0;k<len;k++)(//cout<<t[i].jihe[k]<<"->";move(t[i],k,b);//求move(I,a)//cout<<t[i].jihe[k]<<endl;for(j=0;j<t[i].jihe[k].length();j++)eclouse(t[i].jihe[k][j],t[i].jihe[k],b);//求e-clouse}for(j=0;j<len;j++)(paixu(t[i].jihe[j]);for(k=0;k<h;k++)//paixu(t[i].jihe[j]);for(k=0;k<h;k++)flag=operator==(t[k].ltab,t[i].jihe[j]);if(flag)break;}if(!flag&&t[i].jihe[j].length())t[h++].ltab=t[i].jihe[j];}}cout<<endl<<"状态转换矩阵如下："<<endl;outputfa(len,h,t);//输出状态转换矩阵//状态重新命名string*d=newstring[h];NODE.erase();cout<<endl<<"重命名："<<endl;for(i=0;i<h;i++)(sta=t[i].ltab;t[i].ltab.erase();t[i].ltab='A'+i;NODE+=t[i].ltab;cout<<'('<<sta<<"}="<<t[i].ltab<<endl;for(j=0;j<endnode.length();j++)if(sta.find(endnode[j])<sta.length())d[1]=ednode+=t[i].ltab;for(k=0;k<h;k++)for(m=0;m<len;m++)if(sta==t[k].jihe[m])t[k].jihe[m]=t[i].ltab;for(i=0;i<NODE.length();i++)if(ednode.find(NODE[i])>ednode.length())d[0]+=NODE[i];endnode=ednode;cout<<endl<<"DFA如下："<<endl;outputfa(len,h,t);〃输出DFAcout<<〃其中终态为："<<endnode<<endl;//DFA最小化m=2;sta.erase();flag=0;for(i=0;i<m;i++)(//cout<<"d["<<i<<"]="<<d[i]<<endl;for(k=0;k<len;k++)(//cout<<〃I〃<<CHANGE[k]