確定有窮自動機的最小化問題探討

文章編號：1672-5913(2008)07-0040-03

摘要：本文針對DFA最小化時可能遇到的各種情形，給出最小化的通用算法，并通過具體實例加以驗證。此算法有利于學生對編譯原理課程中DFA最小化的學習和理解，同時讓學生進一步了解此知識點在其他問題求解中的應用。

關鍵詞：有窮自動機(FA)；確定有窮自動機(DFA)；最小化

中圖分類號：G642

文獻標識碼：B

1引言

詞法分析是編譯程序的第一階段，其實質是從描述單詞構成的工具——正規表達式，向識別單詞的工具——確定有限自動機(DFA)的等價轉化。此過程包括正規表達式到非確定有限自動機(NFA)的轉化、NFA到確定有限自動機(DFA)的轉化和DFA的最小化(化簡)三個環節。DFA最小化是轉化的最后一步，也是有限自動機應用及實現方面的重要研究問題之一。它揭示了狀態之間的內在聯系，既方便DFA存儲實現，又可以提高自動識別單詞的效率。本文在分析DFA最小化理論的基礎上，針對轉化過程中可能出現的各種情形，給出求DFA M的最小化DFA M′的一種通用算法，并給出實例加以驗證。

2DFA最小化理論分析

已知一確定有限自動機DFAM，s和t是M的任意兩個不同的狀態。DFA最小化問題涉及到以下幾個重要概念：

1) DFA的最小化定義：是指構造一個與DFA M等價且狀態個數最少的DFA M′，即等價最小DFAM′，有L(M)=L(M′)。

2) 等價狀態：若從狀態s出發能讀出某個字α而停于終態，從狀態t出發也能讀出同一個字α而停于終態；反之，若從t 出發能讀出某個字α而停于終態，則從s出發也能讀出同一個字α而停于終態，則稱s和t為等價狀態。如圖1 中的狀態6和狀態7均只能讀出若干b而停于終態。

也可以定義為，若分別以s和t為始點，到達終態所識別字的字集相等，則稱s和t為等價狀態。如圖1，以狀態6為始點所識別的字集為b*，而以7為始點所識別的字集為bb*，即b*，所以6和7狀態為等價狀態。

3) 可區別狀態：簡言之，如果DFA M中的兩個狀態s、t不等價，則稱s和t是可區別狀態。即：以s和t為始點，到達終態所識別字的字集不相等。

DFA M化簡時的可區別狀態可分為以下三種情形：

●非終態和終態是可區別的。因為，終態識別的字集中一定有ε字而DFA M中的非初態識別的字集中不可能有ε字。

●對同一個字w，s和t兩個狀態，一個到達終態，另一個到達非終態，則s和t可區別。如狀態1和狀態3是可區別的，因為狀態3遇b字符而到達終態6，即能識別字b，而狀態1遇b字符而到達非終態2，即能識別以b開頭的部分字，但不能識別b字。

●s和t兩個狀態，一個有a字符后繼(a∈Σ)，另一個無a字符后繼，則s和t可區別。如狀態2和狀態5是可區別的，因為狀態2有b字符后繼，能識別以b開頭的部分字，而狀態5沒有b字符后繼，不可識別以b開頭的任何字。

3上述概念中，等價狀態和可區別狀態是DFA最小化的兩個重要依據。

3DFA最小化求解算法改進

確定有窮自動機的化簡方法很多，文中以\"分割法\"介紹DFA的化簡：一個DFA M最小化過程是在把M的狀態集分割成一些不相交的子集，使得任何不同的兩子集的狀態都是可區別的，而同一子集的中的任何兩個狀態都是等價的。最后，讓每個子集選出一個代表，同時消除其他等價狀態或者為每一個子集重新命名。

那么給定DFA M，如何形成初始劃分、進一步劃分形成最少狀態數的等價DFA M′？如何解決DFA最小化過程中可能遇到的各種情形？下面介紹一種通用算法。

3.1DFA狀態轉換矩陣的擴展

一個DFA可以表示成一張狀態轉換矩陣。上圖DFA的狀態轉換矩陣如下表1。其 中的許多oslash;元素，表示當前狀態沒有以對應字符為弧的后繼狀態。按照此轉換矩陣，由某一狀態集求其對應字符的后繼狀態集是很方便的，例如I={1，2，3，4，5}，其對應字符的后繼狀態集為I ={1，2，3，4，5}a={3，4， oslash;}，I={1，2，3，4，5}b={2，6，7，oslash;}。

通常在教科書上，初始劃分一般分為兩個子集：終態組和非終態組。然后對形成的每個子集再進一步劃分。但對后繼狀態集中的{oslash;}算法要特殊處理，因為它不屬于任何已劃分子集。現用一種通用算法解決DFA化簡過程中的所有情形：設想在DFA M狀態轉換中有一個出錯狀態e，該狀態為非終止狀態，對于每個狀態，若沒有對應字符為弧的后繼狀態，均引一條弧到達出錯狀態e，并在弧上標注對應字符。擴展后的DFA M如圖2所示，其所對應的狀態轉換矩陣如表2。

3.2 DFA最小化求解算法

依據可區別狀態的定義，可知出錯狀態{e}可區別于終態集和非終態集，因為出錯狀態e識別的字集為空集。因此，可以將初始劃分為三個狀態集(或子集)。改進的DFA最小化算法如下：

已知：DFA M=(K，∑，f，k0，kt)，求最小狀態DFA M′

（1）(1) 構造狀態的初始化劃分∏：

終態kt、非終態K-kt、、出錯狀態e 三個子集

（2）(2) 對∏施用過程PP構造新劃分∏_new

（3）(3) 如果∏_new==∏，則令∏_final=∏并繼續步驟(4)

否則，∏=∏_new，重復(2)

(4) 為∏_final中的每一子集選一代表，這些構成M′的狀態。若k是一代表且f(k，a)=t，令p是t組的代表，則M′中有一轉換f′(k，a)=p。

(5) 刪除其他等價狀態和出錯狀態。

過程PP：構造新的劃分∏_new

① 對∏每一個狀態集G進行下述工作：

將G劃分為子集。G的兩個狀態s和t分在同一子集的充要條件是：對所有的輸入符號a，狀態s和t的a轉換都是∏的同一子集中的狀態。

② 形成的所有子集成為∏_new的狀態子集。

下面以圖1所示的DFA M，利用上述算法將其最小化:

首先將M的狀態分成3個子集：一個由終態(可接受態)組成，一個由非終態組成，一個出錯狀態組成，即初始劃分P0為：P0=({1，2，3，4，5}，{6，7}，{e})，顯然一個子集中的任何狀態與另外兩子集中的任何狀態不等價。

現在觀察第一個子集{1，2，3，4，5}，在讀入輸入符號a后，狀態1、2和5分別轉換為第一個子集中所含的狀態3和4，而3和4分別轉換為第三個子集中所含的狀態e，這就意味著{1，2，5}中的狀態和{3，4}中的任何狀態在讀入a后到達了不等價的狀態，因此{1，2，5}中的任何狀態與{3，4}中的任何狀態都是可區別的，因此得到了新的劃分P1如下：

P1=({1，2，5}，{3，4}，{6，7}，{e})

下面試圖在P1中尋找一個子集和一個輸入符號使得這個子集中的狀態可區別，P1中的子集{1，2，5}對應輸入符號b將其再分割，而得到劃分P2=({1，2}，{3，4}，{5}，{6，7}，{e})。

經過考察，P2不能再劃分了。令1代表{1，2}消去2，令3代表{3，4}，消去4，令6代表{6，7}，消去7，再消去e，我們便得到了圖3的DFA M′，即為圖1 DFA M的最小化。

4 結束語

目前有限自動機理論已廣泛應用于計算理論、編譯技術、模式識別、人工智能等領域，幾乎所有的有限狀態系統都可以用FA來描述。DFA的最小化是有限自動機應用及實現方面的重要問題之一，比起原來的有窮自動機，化簡了的有窮自動機具有較少的狀態，便于其存儲實現，提高自動識別單詞的效率。本文通過具體實例對DFA的最小化進行了詳細的討論，并針對化簡中遇到的各種情形，給出了一種通用、方便的求解算法，可以幫助學生對編譯原理課程中有窮自動機的相關概念有更深入理解，并能針對不同情形完成DFA的最小化。

參考文獻

[1] 張幸兒. 編譯程序構造實踐[M]. 北京:科學出版社，2005.

[2] 呂映芝. 編譯原理[M]. 北京:清華大學出版社.

[3] 馮雁. 編譯原理與技術[M]. 浙江大學出版社，2003.

[4] 劉堅. 編譯原理基礎[M]. 西安電子科技大學出版社，2002.

[5] 朱征宇等. 有限自動機研究的矩陣模型方法[J]. 計算機科學，2001，28(4):46-48.