[NFA到DFA的转化][liliwen919][doc].doc

仲恺农业技术学院编译原理课程设计课程设计题目 ：从ＮFA到ＤFA的转化姓 名　:院(系） :计算机学院　 专业班级 :学 　　　号 : 　　指引教师 ： 设计日期　: 年　9　月15日目 录１.需求分析……………………………………………………………………………2１.1 NＦＡ和ＤFA的概念…………………………………………………………………21.2 NFA和ＤFＡ之间的联系……………………………………………………………22.概要设计……………………………………………………………………………23．具体设计……………………………………………………………………………３3.1 子集构造法………………………………………………………………………33.2 具体转换过程……………………………………………………………………53．3 程序设计…………………………………………………………………………８3.３．1 常量定义………………………………………………………………………８３．3．２ 数据构造定义…………………………………………………………………83.3.3　重要函数流程图………………………………………………………………9４.测试分析…………………………………………………………………………1２５.顾客手册…………………………………………………………………………１4６.课程总结…………………………………………………………………………14参照文献……………………………………………………………………………14附录…………………………………………………………………………………14１.需求分析1.１ NFA和DFＡ的概念NFA（nondeteｒminiｓtic finiｔe－sｔate automａta)即非拟定有限自动机,　一种非拟定的有限自动机ＮFA M’是一种五元式: 　 　 NFＡ　　Ｍ’=(S, Σ∪{ε}, δ, S０， F）其中 Ｓ—有限状态集 　 Σ∪{ε｝—输入符号加上ε,即自动机的每个结点所射出的弧可以是Σ中一种字符或是ε. 　 S０—初态集 　　 　 F—终态集 　　 　　　δ—转换函数 S×Σ　∪{ε}　→2S 　　 (2S　--S的幂集—S的子集构成的集合）DFＡ(determinisｔｉc　ｆinｉtｅ-ｓｔａte　autoｍata)即拟定有限自动机，一种拟定的有限自动机DＦA　Ｍ是一种五元式: 　 M=(Ｓ， Σ，δ,　S0,　Z) 其中： 　 S —有限状态集 　Σ　—输入字母表 　 δ —映射函数（也称状态转换函数）　 　 　　S×Σ→S 　 δ（s，a）=Ｓ’ 　, S, S’ ∈S, ａ∈Σ　 　 S0　—初始状态 　 S0 ∈S　 　 Z—终结状态集 　 　ZÍS１.2 NFＡ和ＤFA之间的联系在非拟定的有限自动机NFＡ中，由于某些状态的转移需从若干个也许的后续状态中进行选择,故一种ＮＦA对符号串的辨认就必然是一种试探的过程。

这种不拟定性给辨认过程带来的反复,无疑会影响到FＡ的工作效率而DFA则是拟定的，将ＮFA转化为DＦA将大大提高工作效率,因此将ＮFA转化为DFA是有其一定必要的２.概要设计通过本课程设计教学所规定达到的目的是:充足理解和掌握NFA，DFＡ以及NFA拟定化过程的有关概念和知识，理解和掌握子集法的有关知识和应用,编程实现对输入NFA转换成DＦA输出的功能程序总框图如图１所示:总控模块NFA图构造状态转换表机构图操作初始化状态转换矩阵状态转换操作图1　程序总框图3.具体设计3.１　子集构造法已证明:非拟定的有限自动机与拟定的有限自动机从功能上来说是等价的，也就是说,我们可以从：ＮFA Ｍ’ 　 　 DFA 　 Ｍ使得　　 L(M)=L(M’)为了使得NFＡ拟定化，我们一方面给出两个定义:定义１:集合I的ε-闭包:令I是一种状态集的子集,定义ε-cｌosure(I）为:1）若s∈Ｉ，则s∈ε－ｃlｏsuｒe(Ｉ）;２）若s∈I,则从s出发通过任意条ε弧可以达到的任何 　状态都属于ε-closure（Ｉ） 　　 　状态集ε-closure（I）称为Ｉ的ε-闭包定义2:令Ｉ是NFA Ｍ’的状态集的一种子集, a∈Σ 　 　　　 　定义: 　Ｉa=ε－clｏｓure(J) 　　 其中J ＝ ∪δ(s，ａ)——Ｊ是从状态子集I中的每个状态出发,通过标记为ａ的弧而达到的状态集合。

——Ｉa是状态子集,其元素为J中的状态，加上从J中每一种状态出发通过ε弧达到的状态给定如图2所示的NFA：bbεaab0123 4图2与之等价的DFＡ如图3：bab{0，1}{2，4}{4}{3}a图３３.2　具体转换过程为了阐明跟清晰，我们使用实例阐明,构造正规式10１（0|1）*011的ＤFA?解:一方面构造相应的NFA,如图４所示:1011εε1001012356478图４将其写成M五元式则为：Ｍ＝({０,1,2，3,4，5,6,7,8}，{0，1｝,δ,0,{8}）其中δ为:　　　 δ（０，1)＝1 　 　　 δ（1,0）＝2 　 δ（2,1）＝3 　　 　　 　δ(3,ε)=4 　 δ(4，ε）＝5 　　 δ(4，0）=4 δ(４,1）＝4　　 　 δ(5,０）＝６ 　 　 δ(6，1）＝7 　 　 δ（７,1）=8 　它所相应的状态转换矩阵如表1:表1状态01ε0ε１ε１２εε2ε３ε3εε4４44556εε６ε7ε7ε8ε8εεε根据NFA转化为DＦA的子集法转换法进行转换,相应的状态转换矩阵见表2：表２ＩI0I１｛0}{ε}｛1}{1｝{２}{ε}{2｝{ε｝{3,4,5}{3，4,５}｛４,５，6}{4，5}｛４，5，6}{4，5，６｝{4,5，７}{4,5}{4，5,6}{４,5}{4，5，7｝{４，5，６}{4,５,8}{4,5,8}｛4,５,6}{4,5}对上表重新命名后的状态转换矩阵见表3：表3IＩ0I10ε1１２ε2ε33４５44６5４5647745将其写成M五元式则为：Ｍ＝（{0，１，2,3，4,5,6,７},｛0,1}，δ，0,｛５｝)其中δ为： 　δ(0，1)=1 　 　　 δ（1，0)=2 　 δ(2,1）=3 　　　 　δ(3,0)＝４　 　 　　 δ（３,1)=5　 　 　 　δ(4,0)＝4 　 　 δ（4,1)＝６ 　 δ(5，0)＝4 　 　 δ(５,1）＝5 　 δ(6,0)=4 　 δ(6,１)＝7　　 　δ（７，0）=4 　δ（７，１）=5　与表3相应的状态转换图如图5所示:110001ε101101236745图5这样就完毕了从正规体现式1０1(０|1)*0１1到DFA的转化。

３.3　程序设计3.３.１ 常量定义#deｆｉne MAX １0#defｉne　ＮumＭaxChａｒ 10#defｉnｅ NumMAXＴＮ 10 #ｄefine　INＦＩNIＴ　3２76７３.3．2 数据构造定义NＦA图构造定义如下：ｔyｐedef　ｓtruct edge{ 　　 　　 　　　 　 　 //边ﻩinｔ dest；ﻩchar　cｏst;ﻩｓtrucｔ ｅdge *link; 　 　 ﻩ//指向下一边}*Ｅdｇe;　ｔｙpedｅｆ　sｔrｕcｔ verｔex{ 　 　 　 　 　 　／/顶点 char　dａta; 　 　 　　 　 　 　 ﻩ//状态 Edge adj;　 　 　 　 　 　 ／/边}*Vertｅx； tｙpeｄef struct　gｒaph{ 　 　 　 　 　　 ／/图ﻩVertｅx ＮodeTａble; ｉｎt NumＶeｒtｅx; ｉｎt ＭaxNumＶertex; inｔ ＮumEdge;}*Gｒａpｈ;状态转换表机构定义如下:typedef ｓtruct tableｎodｅ{ 　 　　　 　 　 　 　　　 　　 //转换表节点ﻩcｈar newnａmｅ； 　 　　 　　　 ／/新命名 char cｈ［MAX]; 　　 　 　　　　　　　 //顶点集合}*ＴablｅＮｏｄe； tｙpｅｄeｆ ｓtrucｔ tａｂｌeｑueuｅ{ 　　　 　 　　 　 　　 　　 　 //转换表列ﻩＴabｌeＮodｅ TN[MＡX]; 　　 　 //转换表节点数组 chaｒ traｎswｏｒd; 　 　 　　　 /／转换条件 ｉnt ＮｕmTn; 　　 　　　　 　　 　 　 　 //添加的顶点数}*TabｌeQuｅue； typｅdeｆ ｓtｒuｃt ｔrａnsmａｔriｘ{ 　 　 　　 　 　 　 　　 　 　 //状态转换矩阵 TablｅQｕｅｕe TＱ; 　 　 　　　　　 　 　/／转换表列组 iｎt transnum； 　　 //转换表列数｝*TranＭatriｘ;3.3.3 重要函数流程图voiｄ Smove函数流程图如图6所示:00非0非00非0开始int i,j,k=0,check,len; Edge p;while(t2[k]!='\0')k++;for(i=0;iNumVertex;j++)if(g->NodeTable[j].data==t1[i]) 。