正規(guī)文法、NFA、DFA、狀態(tài)轉(zhuǎn)換圖、正規(guī)式之間的等價(jià)變換關(guān)系及變換方法-

1、1997年3月第20卷第2期四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版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正規(guī)文法、N FA 、DFA 、狀態(tài)轉(zhuǎn)換圖、正規(guī)式之間的等價(jià)變換關(guān)系及變換方法鄧超成(四川師范大學(xué)計(jì)算機(jī)科學(xué)系成都610066摘要正規(guī)文法、N FA 、D FA 、狀態(tài)轉(zhuǎn)換圖、正規(guī)式是形式語言理論的基礎(chǔ)概念,也是編譯原理詞法分析理論中的重要概念和工具.本文討論了它們之間的等價(jià)變換關(guān)系,給出了變換的具體方法并簡介了它們的用途.關(guān)鍵詞正規(guī)文法,N

2、FA ,D FA ,狀態(tài)轉(zhuǎn)換圖,正規(guī)式,等價(jià)變換中圖法分類號T P 301.2在編譯原理詞法分析理論中,均要涉及到正規(guī)文法、N FA 、DFA 、狀態(tài)轉(zhuǎn)換圖、正規(guī)式這幾個(gè)重要內(nèi)容.它們分別在詞法分析及詞法分析器自動(dòng)生成的理論研究、表示及實(shí)現(xiàn)等方面,起著重要作用.本文將完整地給出它們之間的等價(jià)變換關(guān)系和具體的變換方法.1正規(guī)文法與N FA 間的等價(jià)變換由正規(guī)文法G 所描述的語言L (G 和對應(yīng)的N FA M 所識別的語言L (M 之間存在等價(jià)性(其證明見參考文獻(xiàn)1,故可構(gòu)造正規(guī)文法到N FA 的轉(zhuǎn)換方法.反之,亦可從N FA 轉(zhuǎn)換到正規(guī)文法.兩者之間的轉(zhuǎn)換方法為文法產(chǎn)生式與N FA 的W 函數(shù)的

3、對應(yīng)轉(zhuǎn)換(見參考文獻(xiàn)2,3.可知,正規(guī)文法與N FA 之間可等價(jià)轉(zhuǎn)換.2N FA 與DFA 間的等價(jià)變換由N FA M 所識別的語言L (M 和對應(yīng)的DFA M 所識別的語言L (M 之間存在等價(jià)性(其證明見參考文獻(xiàn)1,并可用子集法和等價(jià)類劃分法把N FA 轉(zhuǎn)換為等價(jià)的最小化的DFA (其轉(zhuǎn)換方法見參考文獻(xiàn)2,3.又由正規(guī)文法NFA,N FA DFA,所以正規(guī)文法與DFA 間可等價(jià)轉(zhuǎn)換(其轉(zhuǎn)換方法見參考文獻(xiàn)2,3.3N FA 與狀態(tài)轉(zhuǎn)換圖間的等價(jià)變換由狀態(tài)轉(zhuǎn)換圖的定義,可知狀態(tài)轉(zhuǎn)換圖只不過是N FA 的圖形化表示,與N FA 是一一對應(yīng)的.故N FA 可等價(jià)的轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換圖,反之,狀態(tài)轉(zhuǎn)換圖

4、亦可轉(zhuǎn)換為N FA.即N FA 與狀態(tài)轉(zhuǎn)換圖間可等價(jià)變換,且它們之間的轉(zhuǎn)換方法是W 函數(shù)與圖形化表示的一一對應(yīng).又由正規(guī)文法N FA,N FA 狀態(tài)轉(zhuǎn)換圖,所以正規(guī)文法與狀態(tài)轉(zhuǎn)換圖間亦可等價(jià)轉(zhuǎn)換.下面給出正規(guī)文法與狀態(tài)轉(zhuǎn)換圖間的相互轉(zhuǎn)換方法(產(chǎn)生式與圖結(jié)點(diǎn)和邊的對應(yīng)轉(zhuǎn)換法:記正規(guī)文法G 中的開始符號S V N 為狀態(tài)轉(zhuǎn)換圖中的初始狀態(tài)結(jié)點(diǎn)q 0Q ,正規(guī)文法G 中的其余非終結(jié)符A i V N 為狀態(tài)轉(zhuǎn)換圖中的狀態(tài)結(jié)點(diǎn)q i Q ,用表示狀態(tài)轉(zhuǎn)換圖中的終態(tài)結(jié)點(diǎn),T i F 為終態(tài),則正規(guī)文法G 產(chǎn)生式集P 中的產(chǎn)生式,可由下述規(guī)則轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換圖中的狀態(tài)結(jié)點(diǎn)和邊:(i 對P 中每一條形如A i

5、aB j 的產(chǎn)生式,轉(zhuǎn)換為q i aq j;(ii 對P 中每一條形如A i a 的產(chǎn)生式,轉(zhuǎn)換為q i aT j;(iii 對P 中每一條形如A i X 的產(chǎn)生式,若A i V N 且A i S ,轉(zhuǎn)換為q i ;(iv 對P 中產(chǎn)生式SX ,轉(zhuǎn)換為q 0.按照上述規(guī)則,正規(guī)文法G 一定可等價(jià)轉(zhuǎn)換為對應(yīng)的狀態(tài)轉(zhuǎn)換圖T.反之,按照上述規(guī)則,狀態(tài)轉(zhuǎn)換圖T 一定可等價(jià)轉(zhuǎn)換為對應(yīng)的正規(guī)文法G .4N FA 與正規(guī)式間的等價(jià)變換由N FA M 所識別的語言L(M 和對應(yīng)的正規(guī)式R 所描述的語言L(R之間存在等價(jià)性(其證明見參考文獻(xiàn)1-3,并可用指定的算法(規(guī)則把正規(guī)式轉(zhuǎn)換為N FA(其算法見參考文獻(xiàn)2

6、,3.下面給出把N FA M 轉(zhuǎn)換為正規(guī)式R 的方法(按轉(zhuǎn)換規(guī)則逐步壓縮法:設(shè)q i Q ,i =1,2,n ,q 0Q 為初態(tài),q f F 為終態(tài),a j V T ,j =1,2,n ,為E 上的單個(gè)終結(jié)符,k k V *T ,k =1,2,n ,為E *上的終結(jié)符串,正規(guī)式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開始,反復(fù)利用(1把多個(gè)形如r i ,j 、r j ,k 的符號串k k i 聯(lián)結(jié)成為串k k 1k k 2k k n ,直至聯(lián)結(jié)到r i ,f 為止.所得串即為R 中的一個(gè)獨(dú)立項(xiàng)R i ,所有的R i 便組成正規(guī)式R =R 1|R 2|R n .(3將(2中所得諸R i 中的公共部分作為公因子

8、分別提出、合并、整理便可得到規(guī)范的正規(guī)式R.又由正規(guī)文法N FA,N FA 正規(guī)式,所以正規(guī)文法和正規(guī)式間可等價(jià)轉(zhuǎn)換.正規(guī)文法可用正規(guī)方程式聯(lián)立求解的方法,轉(zhuǎn)換為正規(guī)式(其具體作法見參考文獻(xiàn)2,3.而正規(guī)式轉(zhuǎn)換90四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版20卷為正規(guī)文法,可借助于對應(yīng)的N FA 實(shí)現(xiàn),即正規(guī)式N FA 正規(guī)文法.5轉(zhuǎn)換關(guān)系圖通過上述討論,可知正規(guī)文法、N FA 、DFA 、狀態(tài)轉(zhuǎn)換圖和正規(guī)式它們之間的轉(zhuǎn)換關(guān)系可用圖1表示:圖結(jié)點(diǎn)和邊轉(zhuǎn)換成對應(yīng)的產(chǎn)生式產(chǎn)生式轉(zhuǎn)換成對應(yīng)的圖結(jié)點(diǎn)和邊圖中結(jié)點(diǎn)函數(shù)化W 函數(shù)圖形化W 函數(shù)轉(zhuǎn)換成對應(yīng)的產(chǎn)生式當(dāng)正規(guī)文法G 本身為DFA 時(shí),產(chǎn)生式轉(zhuǎn)換成對應(yīng)的函數(shù)狀態(tài)轉(zhuǎn)

9、換圖W 函數(shù)轉(zhuǎn)換成對應(yīng)的產(chǎn)生式當(dāng)正規(guī)文法G 為最小DFA 時(shí)產(chǎn)生式轉(zhuǎn)換成對應(yīng)的函數(shù)按轉(zhuǎn)換規(guī)則逐步細(xì)化按轉(zhuǎn)換規(guī)則逐步壓縮產(chǎn)生式轉(zhuǎn)換為正規(guī)方程后聯(lián)立求解正規(guī)式最小DFA等價(jià)類劃分法DFA子集法NFAW 函數(shù)轉(zhuǎn)換成對應(yīng)的產(chǎn)生式產(chǎn)生式轉(zhuǎn)換成對應(yīng)的W 函數(shù)正規(guī)文法圖1轉(zhuǎn)換關(guān)系圖6用途(i 正規(guī)文法是正規(guī)語言(正規(guī)集的形式化描述,用于正規(guī)語言的形式化表示和理論研究.(ii 有窮自動(dòng)機(jī)FA (N FA 和DFA 是具有有限個(gè)記憶的離散動(dòng)態(tài)系統(tǒng)的形式模型,用于數(shù)字計(jì)算機(jī)、圖形識別、信息和編碼以及神經(jīng)過程等的形式模型表示和研究.在編譯原理的詞法分析中,用于單詞識別、生成過程的模型表示和實(shí)現(xiàn).(iii 狀態(tài)轉(zhuǎn)換圖

10、是正規(guī)文法、有窮自動(dòng)機(jī)FA 的圖形表示,直觀易懂,與通常的程序流程圖很相近,易于實(shí)現(xiàn)程序的編制.(iv 正規(guī)式是正規(guī)文法、有窮自動(dòng)機(jī)FA 的代數(shù)化表示,它的表示準(zhǔn)確、緊湊、高效,可以構(gòu)造高效的詞法分析器.用于詞法分析器的自動(dòng)生成,也用于各種信息(如模式識別、情報(bào)檢索91第2期鄧超成:正規(guī)文法、N FA 、D FA 、狀態(tài)轉(zhuǎn)換圖、正規(guī)式之間的等價(jià)變換關(guān)系及變換方法等的處理.參考文獻(xiàn)1鄒海明,周新.形式語言、自動(dòng)機(jī)和語法分析.湖北:華中工學(xué)院出版社,19852陳火旺,錢家驊,孫永強(qiáng).程序設(shè)計(jì)語言編譯原理.北京:國防工業(yè)出版社,19843肖軍模.程序設(shè)計(jì)語言編譯方法.遼寧:大連理工大學(xué)出版社,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