正规文法、NFA、DFA、状态转换图、正规式之间的等价变换关系及变换方法-

1、1997年3月第20卷第2期四川师范大学学报(自然科学版Jour nal of Sichuan N or mal U niv e rsity (N atura l ScienceV o l.20,N o.2M ar.,1997收稿日期1996-12-03正规文法、N FA 、DFA 、状态转换图、正规式之间的等价变换关系及变换方法邓超成(四川师范大学计算机科学系成都610066摘要正规文法、N FA 、D FA 、状态转换图、正规式是形式语言理论的基础概念,也是编译原理词法分析理论中的重要概念和工具.本文讨论了它们之间的等价变换关系,给出了变换的具体方法并简介了它们的用途.关键词正规文法,N

2、FA ,D FA ,状态转换图,正规式,等价变换中图法分类号T P 301.2在编译原理词法分析理论中,均要涉及到正规文法、N FA 、DFA 、状态转换图、正规式这几个重要内容.它们分别在词法分析及词法分析器自动生成的理论研究、表示及实现等方面,起着重要作用.本文将完整地给出它们之间的等价变换关系和具体的变换方法.1正规文法与N FA 间的等价变换由正规文法G 所描述的语言L (G 和对应的N FA M 所识别的语言L (M 之间存在等价性(其证明见参考文献1,故可构造正规文法到N FA 的转换方法.反之,亦可从N FA 转换到正规文法.两者之间的转换方法为文法产生式与N FA 的W 函数的

3、对应转换(见参考文献2,3.可知,正规文法与N FA 之间可等价转换.2N FA 与DFA 间的等价变换由N FA M 所识别的语言L (M 和对应的DFA M 所识别的语言L (M 之间存在等价性(其证明见参考文献1,并可用子集法和等价类划分法把N FA 转换为等价的最小化的DFA (其转换方法见参考文献2,3.又由正规文法NFA,N FA DFA,所以正规文法与DFA 间可等价转换(其转换方法见参考文献2,3.3N FA 与状态转换图间的等价变换由状态转换图的定义,可知状态转换图只不过是N FA 的图形化表示,与N FA 是一一对应的.故N FA 可等价的转换为状态转换图,反之,状态转换图

4、亦可转换为N FA.即N FA 与状态转换图间可等价变换,且它们之间的转换方法是W 函数与图形化表示的一一对应.又由正规文法N FA,N FA 状态转换图,所以正规文法与状态转换图间亦可等价转换.下面给出正规文法与状态转换图间的相互转换方法(产生式与图结点和边的对应转换法:记正规文法G 中的开始符号S V N 为状态转换图中的初始状态结点q 0Q ,正规文法G 中的其余非终结符A i V N 为状态转换图中的状态结点q i Q ,用表示状态转换图中的终态结点,T i F 为终态,则正规文法G 产生式集P 中的产生式,可由下述规则转换为状态转换图中的状态结点和边:(i 对P 中每一条形如A i

5、aB j 的产生式,转换为q i aq j;(ii 对P 中每一条形如A i a 的产生式,转换为q i aT j;(iii 对P 中每一条形如A i X 的产生式,若A i V N 且A i S ,转换为q i ;(iv 对P 中产生式SX ,转换为q 0.按照上述规则,正规文法G 一定可等价转换为对应的状态转换图T.反之,按照上述规则,状态转换图T 一定可等价转换为对应的正规文法G .4N FA 与正规式间的等价变换由N FA M 所识别的语言L(M 和对应的正规式R 所描述的语言L(R之间存在等价性(其证明见参考文献1-3,并可用指定的算法(规则把正规式转换为N FA(其算法见参考文献2

6、,3.下面给出把N FA M 转换为正规式R 的方法(按转换规则逐步压缩法:设q i Q ,i =1,2,n ,q 0Q 为初态,q f F 为终态,a j V T ,j =1,2,n ,为E 上的单个终结符,k k V *T ,k =1,2,n ,为E *上的终结符串,正规式R 形如R 1|R 2|R n ,R i V *T ,若L(M =X ,则R =X ;若L(M =a ,则R=a ;若有W (q i ,a m =q j ,i j ,i ,j 0,则记为r i ,j =a m ;若有W (q i ,a m =q i ,i 0,则记为r i ,i =a *m ;若有W (q i ,a m

7、=q f ,i 0,则记为r i ,f =a m .(1若r i ,j =a m ,r j ,k =a n ,则r i ,k =a m a n =k k ,i ,j ,k 0且不相等;若r i ,j =a m ,r j ,i =a n ,则r i ,i =(a m a n *=k *i .(2从i =0开始,反复利用(1把多个形如r i ,j 、r j ,k 的符号串k k i 联结成为串k k 1k k 2k k n ,直至联结到r i ,f 为止.所得串即为R 中的一个独立项R i ,所有的R i 便组成正规式R =R 1|R 2|R n .(3将(2中所得诸R i 中的公共部分作为公因子

8、分别提出、合并、整理便可得到规范的正规式R.又由正规文法N FA,N FA 正规式,所以正规文法和正规式间可等价转换.正规文法可用正规方程式联立求解的方法,转换为正规式(其具体作法见参考文献2,3.而正规式转换90四川师范大学学报(自然科学版20卷为正规文法,可借助于对应的N FA 实现,即正规式N FA 正规文法.5转换关系图通过上述讨论,可知正规文法、N FA 、DFA 、状态转换图和正规式它们之间的转换关系可用图1表示:图结点和边转换成对应的产生式产生式转换成对应的图结点和边图中结点函数化W 函数图形化W 函数转换成对应的产生式当正规文法G 本身为DFA 时,产生式转换成对应的函数状态转

9、换图W 函数转换成对应的产生式当正规文法G 为最小DFA 时产生式转换成对应的函数按转换规则逐步细化按转换规则逐步压缩产生式转换为正规方程后联立求解正规式最小DFA等价类划分法DFA子集法NFAW 函数转换成对应的产生式产生式转换成对应的W 函数正规文法图1转换关系图6用途(i 正规文法是正规语言(正规集的形式化描述,用于正规语言的形式化表示和理论研究.(ii 有穷自动机FA (N FA 和DFA 是具有有限个记忆的离散动态系统的形式模型,用于数字计算机、图形识别、信息和编码以及神经过程等的形式模型表示和研究.在编译原理的词法分析中,用于单词识别、生成过程的模型表示和实现.(iii 状态转换图

10、是正规文法、有穷自动机FA 的图形表示,直观易懂,与通常的程序流程图很相近,易于实现程序的编制.(iv 正规式是正规文法、有穷自动机FA 的代数化表示,它的表示准确、紧凑、高效,可以构造高效的词法分析器.用于词法分析器的自动生成,也用于各种信息(如模式识别、情报检索91第2期邓超成:正规文法、N FA 、D FA 、状态转换图、正规式之间的等价变换关系及变换方法等的处理.参考文献1邹海明,周新.形式语言、自动机和语法分析.湖北:华中工学院出版社,19852陈火旺,钱家骅,孙永强.程序设计语言编译原理.北京:国防工业出版社,19843肖军模.程序设计语言编译方法.辽宁:大连理工大学出版社,199

11、5T HE EQ U IV A LEN T RELA T IO N AN D T RAN SFO RM A T IO N M ET HO D O F REG U L A R G RAM M A R ,N FA ,DFA ,ST A T E TR AN SITIO N DIAG RAM AN D REGU LA R EX PRESSIO NDeng Chaocheng(Depar tment of Comp uter Sciences ,Sich uan Normal University ,Chengd u 610066,Sichuan Abstract In this paper ,the equiv alent t ransfor matio n rela tio n o f Regular g ra mma r ,N F A,D F A,State tr ansitio n diag ra m and Reg ula r ex pressio n is a rg ued.Th e co nc rete methods of transfo rmation is presented.Key words Reg ul