资源描述：
《正规文法_NFA_DFA_状态转换图_正规式之间的等价变换关系及变换方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1997年3月四川师范大学学报(自然科学版)Vol.20,No.2第20卷第2期JournalofSichuanNormalUniversity(NaturalScience)Mar.,1997正规文法、NFA、DFA、状态转换图、正规式之间的等价变换关系及变换方法邓超成(四川师范大学计算机科学系成都610066)摘要正规文法、NFA、DFA、状态转换图、正规式是形式语言理论的基础概念,也是编译原理词法分析理论中的重要概念和工具.本文讨论了它们之间的等价变换关系,给出了变换的具体方法并简介了它们的用途.关键词正规文法,NFA,DFA,状态转换图,正规式,等价变换
2、中图法分类号TP301.2在编译原理词法分析理论中,均要涉及到正规文法、NFA、DFA、状态转换图、正规式这几个重要内容.它们分别在词法分析及词法分析器自动生成的理论研究、表示及实现等方面,起着重要作用.本文将完整地给出它们之间的等价变换关系和具体的变换方法.1正规文法与NFA间的等价变换由正规文法G所描述的语言L(G)和对应的NFAM所识别的语言L(M)之间存在等价性(其证明见参考文献[1]),故可构造正规文法到NFA的转换方法.反之,亦可从NFA转换到正规文法.两者之间的转换方法为文法产生式与NFA的D函数的对应转换(见参考文献[2,3]).可知,正规文法与
3、NFA之间可等价转换.2NFA与DFA间的等价变换由NFAM所识别的语言L(M)和对应的DFAM′所识别的语言L(M′)之间存在等价性(其证明见参考文献[1]),并可用子集法和等价类划分法把NFA转换为等价的最小化的DFA(其转换方法见参考文献[2,3]).又由正规文法≡NFA,NFA≡DFA,所以正规文法与DFA间可等价转换(其转换方法见参考文献[2,3]).3NFA与状态转换图间的等价变换由状态转换图的定义,可知状态转换图只不过是NFA的图形化表示,与NFA是一一对应的.故NFA可等价的转换为状态转换图,反之,状态转换图亦可转换为NFA.即NFA与状态转换图
4、间可等价变换,且它们之间的转换方法是D函数与图形化表示的一一对应.收稿日期199621220390四川师范大学学报(自然科学版)20卷又由正规文法≡NFA,NFA≡状态转换图,所以正规文法与状态转换图间亦可等价转换.下面给出正规文法与状态转换图间的相互转换方法(产生式与图结点和边的对应转换法):记正规文法G中的开始符号S∈VN为状态转换图中的初始状态结点q0∈Q,正规文法G中的其余非终结符Ai∈VN为状态转换图中的状态结点qi∈Q,用○○表示状态转换图中的终态结点,Ti∈F为终态,则正规文法G产生式集P中的产生式,可由下述规则转换为状态转换图中的状态结点和边:a
5、(i)对P中每一条形如AiaBj的产生式,转换为○qi○qj;a(ii)对P中每一条形如Aia的产生式,转换为○qi○○Tj;(iii)对P中每一条形如AiE的产生式,若Ai∈VN且Ai≠S,转换为○qi;(iv)对P中产生式SE,转换为○○q0.按照上述规则,正规文法G一定可等价转换为对应的状态转换图T.反之,按照上述规则,状态转换图T一定可等价转换为对应的正规文法G.4NFA与正规式间的等价变换由NFAM所识别的语言L(M)和对应的正规式R所描述的语言L(R)之间存在等价性(其证明见参考文献[1-3]),并可用指定的算法(规则)把正规式转换为NFA(其算法见
6、参考文献[2,3]).下面给出把NFAM转换为正规式R的方法(按转换规则逐步压缩法):设qi∈Q,i=1,2,⋯,n,q0∈Q为初态,qf∈F为终态,aj∈VT,j=1,2,⋯,n,为2上的单个终结符,33Xk∈VT,k=1,2,⋯,n,为2上的终结符串,3正规式R形如R1ûR2û⋯ûRn,Ri∈VT,若L(M)=E,则R=E;若L(M)=a,则R=a;若有D(qi,am)=qj,i≠j,i,j≥0,则记为ri,j=am;3若有D(qi,am)=qi,i≥0,则记为ri,i=am;若有D(qi,am)=qf,i≥0,则记为ri,f=am.(1)若ri,j=am,
7、rj,k=an,则ri,k=aman=Xk,i,j,k≥0且不相等;33若ri,j=am,rj,i=an,则ri,i=(aman)=Xi.(2)从i=0开始,反复利用(1)把多个形如ri,j、rj,k的符号串Xk联结成为串XkXk⋯Xk,i12n直至联结到ri,f为止.所得串即为R中的一个独立项Ri,所有的Ri便组成正规式R=R1ûR2û⋯ûRn.(3)将(2)中所得诸Ri中的公共部分作为公因子分别提出、合并、整理便可得到规范的正规式R.又由正规文法≡NFA,NFA≡正规式,所以正规文法和正规式间可等价转换.正规文法可用正规方程式联立求解的方法,转换为正规式(其
8、具体作法见参考文献[2,
