自動機與正規(guī)式相互轉換的方法

摘要：本文主要介紹基于編譯器構造技術中的由正規(guī)表達式到最小化DFA的算法設計和實現(xiàn)技術，以及自動機轉換正規(guī)式的方法。正規(guī)式與自動機理論以不同方式表達相同語言，兩者相互轉換在編譯器構造過程中起至關重要的作用，也被廣泛應用于計算機科學的各個領域。

關鍵詞：DFA；NFA；正規(guī)表達式；子集構造法

中圖分類號：TP314文獻標識碼：A文章編號：1009-3044(2008)20-30221-03

The Method how Finite Automata and Regular Expression Switch each other

MIAO Yu

(Zhuhai College，Jilin University，Zhuhai 519041，China)

Abstract:This thesis introduces the arithmetic design that how regular expression switches to minimum state DFA and the method how finite automata switches to regular expression. Regular expression and finite automata theory have different fashion to express the same language. They are more important in compiler formation and also have a lot of application in the other fields of computer science.

Key words:DFA;NFA;regular expression;Subset Construction Algorithm

1 引言

編譯原理與技術的一整套理論在整個計算機科學領域占有相當重要的地位。學習它，對程序設計人員有很大的幫助。研究編譯原理中的算法可以幫助我們更加深層次的理解程序語言和內部機制，可以用來做簡單的命令解釋器，比如游戲的腳本引擎。而且，界面開發(fā)也需要編譯原理的知識。

2 正規(guī)表達式、有限自動機的關系

正規(guī)表達式和有限自動機概念是編譯原理中很重要的部分，兩者有替代關系，正規(guī)式可以描述的語言就有自動機可以測試，自動機可以描述同樣的語言。這就是說，正規(guī)式所表示的語言即正規(guī)集與有限自動機所識別的語言是完全等價的，只是表示形式不同而已。同一個語言，既可以用自動機描述，也可以用正規(guī)式描述。

3 正規(guī)式到有限自動機的轉換

3.1 轉換步驟

要把正規(guī)表達式轉換為最小化狀態(tài)DFA，可以直接通過相關算法轉換，設計過程非常復雜。整個過程通過下列三個步驟實現(xiàn)：

(1)由正規(guī)表達式構造NFA；

(2)把NFA轉化為與其等價的DFA；

(3)把DFA最小化。

3.1.1正則表達式轉換為NFA的分析設計過程

由正規(guī)表達式構造NFA：使用Thompson構造法:

輸入：字母表∑上的一個正規(guī)表達式r。

輸出：接受L(r)的NFA N。

3.1.2 NFA轉換為DFA的分析設計過程

使用子集構造算法：

輸入：一個NFA N；

輸出：一個接受同樣語言的DFA D。

方法：為D構造轉換表Dtran，DFA的每個狀態(tài)是NFA的狀態(tài)集，D“并行”地模擬N對輸入串的所有可能的移動。

用表1的運算來計算NFA狀態(tài)集的變化。S代表NFA的狀態(tài)，T代表NFA的狀態(tài)集。

(1)構造NFAN的子集構造的算法：

算法構造D的狀態(tài)集合Dstates和轉換表Dtran。D的每個狀態(tài)對應于NFA的一個狀態(tài)集合，它是N讀了某個符號串后所能達到的全部狀態(tài)，包括e轉換后的所有狀態(tài)。D的開始狀態(tài)是e-closure(S0)。如果D的狀態(tài)是至少含N的一個接受狀態(tài)的狀態(tài)集，那么它是D的一個接受狀態(tài)。

開始，令e-closure(S0)為Dstates中唯一成員，并且它是未被標記的；

while （Dstates中存在尚未被標記的子集T）do begin

標記T；

for 每個輸入字母a do begin{

U:= ε-closure(move(T，a))；

ifU不在Dstates中 then

將U作為未標記的子集加在C中；

Dtran[T，a]:=U}

end

end

(2)ε-closure的計算：

將T中所有的狀態(tài)壓入棧stack中；

將ε-closure（T）初始化為T；

While 棧stack不空do begin

將棧頂元素t彈出棧；

for每個這樣的狀態(tài)u：從t到u有一條標記為ε的邊do

if u不在ε-closure（T）內 do begin

將u添加到ε-closure（T）；

將u壓入棧stack中

End

End

3.1.3 最小化DFA狀態(tài)數(shù)的分析設計過程

最小化DFA狀態(tài)數(shù)的算法：

輸入：DFAM（其狀態(tài)集合為S），輸入符號為∑，轉換函數(shù)為f：S×∑->S，開始狀態(tài)為s0，接受狀態(tài)集為F。

輸出：一個DFAM＇，它和M接受同樣的語言，且狀態(tài)數(shù)最少。

方法：

(1)構造具有兩個組的狀態(tài)集合的初始劃分∏：接受狀態(tài)組F，非接受狀態(tài)組S-F。

(2)對∏采用下面所述的過程來構造新的劃分∏new。

for ∏中的每個組Gdo begin

當且僅當對任意輸入符號a，狀態(tài)s和t在a上的轉換到達∏中的同一組中的狀態(tài)時，才把G劃分成小組，以便G的兩個狀態(tài)s和t在同一小組中；最壞情況下，一個狀態(tài)就可能成為一個組。

用所有新形成的小組集代替∏new中的G；

end

(3)如果∏new=∏，令∏final:=∏，再執(zhí)行步驟4；否則，令∏=∏new，重復步驟2。

(4)在劃分∏final的每個狀態(tài)組中選一個狀態(tài)作為該組的代表，這些代表構成了簡化后的DFA M＇的狀態(tài)。令s是一個代表狀態(tài)，而且假設：在DFA M中，在輸入a上有從s到t的轉換。令t所在組的代表是r（r可能就是t），那么在M＇中有一個從s到r的a上的轉換。令包含s0 的狀態(tài)組的代表是M＇的開始狀態(tài)，并令M＇的接受狀態(tài)是那些屬于F集的狀態(tài)所在組的代表。注意，∏final的每個組或者僅含F(xiàn)中的狀態(tài)，或者不含F(xiàn)中的狀態(tài)。

(5)如果M＇含有死狀態(tài)（即一個對所有輸入符號都有到自身的轉換的非接受狀態(tài)d），即從M＇中去掉它；刪除從開始狀態(tài)不可到達的狀態(tài)；取消從任何其它狀態(tài)到死狀態(tài)的轉換定義。

使用這個算法時，輸入DFA狀態(tài)轉換函數(shù)必須是全函數(shù)。

4 由自動機轉換成正規(guī)式

正規(guī)式所表示的語言即正規(guī)集與有限自動機所識別的語言是完全等價的，只是表示形式不同而已。同一個語言，既可以用自動機描述，也可以用正規(guī)式描述。

如果狀態(tài)數(shù)是有限的，輸入的字符集已知，開始狀態(tài)，終止狀態(tài)確定，轉換函數(shù)可以得到的情況下，可以把這一類的語言直接描述成自動機，如果需要通過正規(guī)式描述則可以通過自動機轉化成正規(guī)式的算法。

4.1自動機M向正規(guī)式轉化算法

(1)把狀態(tài)轉換圖的概念拓廣，令每條弧上都可以用一個正規(guī)式作標記。

(2)在M的轉換圖上加兩個節(jié)點：x，y。從x用ε弧連接到M的所有初始節(jié)點；從M的終止節(jié)點用ε弧連接到y(tǒng)，新的NFA為M＇，且L（M）＝L(M＇)。

(3)逐步消除M＇中的所有節(jié)點，直到只剩下x，y為止，在x至y的弧上標記的正規(guī)式就是M接受的正規(guī)式。

5 結束語

正則表達式是一種可以用于模式匹配和替換的強有力的工具。例如搜索引擎就用到正則表達式的模式匹配功能。同時我們可以在幾乎所有的基于UNIX系統(tǒng)的工具中找到正則表達式的身影，例如，vi編輯器，Perl或PHP腳本語言，以及awk或sed shell程序等。由此可見，對正則表達式的研究已經超出了某種語言或某個系統(tǒng)的局限。

自動機是正則表達式的另一種形式，自動機可以應用到二次平臺的開發(fā)，工業(yè)控制等領域，自動機和正則表達式的相互轉換理論使得它們的應用領域更加廣闊。

參考文獻：

[1] Alfred V Aho，Ravi Sethi，Jeffrey D Ullman.編譯原理 技術與工具[M].2版.北京:人民郵電出版社，2008.

[2] Kenneth C.Louden.編譯原理與實踐[M].北京:機械工業(yè)出版社，2002.

[3] 陳意云.編譯原理[M].北京:高等教育出版社，2003.

[4] 金成植.編譯程序構造原理和實現(xiàn)技術[M].北京:高等教育出版社，2000.