ＤＦＡ最小化算法的探討與改進

文章編號：1672-5913(2008)09-0071-02

摘要：很多編譯原理教材介紹的DFA最小化算法是“分割法”，但該算法存在一定的問題，本文結合實例分析該算法的漏洞所在，并提出了改進的算法。

關鍵詞：編譯原理；DFA；分割法

中圖分類號：G642

文獻標識碼：B

引言

“編譯原理”是計算機專業的一門綜合性較強的專業課程，主要介紹如何將高級語言翻譯為低級語言的編譯程序的工作原理和實現技術。該課程建立在高級語言或匯編語言基礎上，綜合運用編譯理論及數據結構、離散數學等前修課程的相關知識，具有很強的理論性和嚴密的邏輯性，可以使學生真正了解計算機的工作過程，對提高學生計算機軟件素質具有很大作用。本文結合教學工作實際，針對詞法分析中確定的有窮自動機(DFA)的最小化算法和具體的做法進行深入的探討，并對現有算法進行了合理的改進。

1DFA及DFA的化簡

編譯程序一般包括詞法分析、語法分析、語義分析、中間代碼生成、目標代碼生成、代碼優化、表格管理和出錯處理等成分。詞法分析是編譯程序要做的首要工作，它接收輸入的源程序符號串，按照構詞規則分割為一個個的單詞符號并輸出。

有窮自動機是一種能進行運算和自我控制的裝置，能準確識別單詞符號。因此，可以通過構造有窮自動機來實現詞法分析程序的自動構造。有窮自動機分為確定的有窮自動機DFA和不確定的有窮自動機NFA兩種。

定義1DFA 一個確定的有窮自動機M是一個五元組，M=( K，Σ， f ， S ， Z)，其中：K是一個有窮集，其元素稱為狀態；Σ是一個有窮字母表，其元素稱為輸入符號；S∈K，稱為初態；ZIgrave; K，是終態集；f是轉換函數，是K×Σ→K上的映射，f(ki，a)=kj，(ki∈K，kj∈K)表示狀態ki，輸入符為a時，轉換為狀態kj。

定義2無用狀態從自動機的開始狀態出發，任何輸入串也不能到達的那個狀態;或者從這個狀態沒有通路到達終態的狀態。

定義3等價狀態如果說兩個狀態s 和t 是等價的， 應滿足如下條件：(a) 一致性條件：s 和t 必須同時為終態或為非終態；(b) 蔓延性條件：對于所有輸入符號，狀態s 和t 必須轉換到等價的狀態里。

一個DFAM可以通過消除無用狀態和合并等價狀態而轉化為一個最小化的與之等價的DFAM’。該過程稱為DFA的化簡。

2“分割法”化簡DFA

對一個DFAM最少化的基本思想是：把M的狀態集劃分為一些不相交的子集，使得任何兩個不同子集中的狀態是(可區別)不等價的，而同一子集的任何兩個狀態是等價的。具體算法過程描述如下：

(1) 把S劃分為終態和非終態兩個子集，形成初始劃分P；

(2) 假定P已含m個子集，記為P= { I1 ， I2 ， #8943;， Im}，則對每一個Ii 和每一個a ∈Σ考察： I i a = f ( I i ， a) ，如I i a 中的狀態分別落于P中P 個不同的子集，則子集I i 將被P 個更小的狀態子集I i1 ， I i2 ， #8943;， I i p 所細分。令細分后所得的狀態集合為Pnew；

(3) 重復步驟(2 )直到直至所含的子集數不再增加為止，Pnew =P；

(4) 對P中的每個子集I i ，若該子集包含原有的初態，則此代表狀態便為最小化后M 的初態；該子集包含原有的終態，則此狀態便為最小化后的終態；

(5) 刪去狀態集中的所有死狀態，即得到化簡后的M’。

下面我們通過一個例子來看一下該算法中存在的問題。

例1假定DFA M 如下圖1所示。

使用上述算法進行化簡M：初始劃分P0={{0}，{1，2}}，此時P0含有兩個子集I1和I2，I1不可再分，由于I2a=I2b=2∈I2，沒有新集合增加，故可以得到化簡后的M’，如圖2所示。

圖1 DFA M

圖2 DFA M’

化簡后的M’與原來的M是否等價呢？顯然，對于符號串ba，原來的DFAM不能識別，而化簡后的M’能夠識別，這說明二者并不等價。

3DFA最小化算法的改進

通過分析上述化簡過程，我們可以找出算法問題所在。算法步驟2中涉及到集合運算，而忽略了空集對于算法的影響。根據定義3，要判斷兩個狀態是否等價必須對于所有輸入符號檢查一遍，看它們分別轉到等價的狀態中，如上面例1中狀態1不能接受a而狀態2能接受a，顯然二者不等價。而在算法中，把狀態子集{1，2}在接受a后還是轉到它自身，所以就出現錯誤了。

某個狀態下不能接受某個輸入符號即為出錯，故上述算法沒有考慮到出錯情況。因此我們可以對上述算法進行如下改進：

(1) 增加一個出錯狀態error，把S劃分為終態、非終態、出錯三個子集，形成初始劃分P；

(2) 對于P中每個子集Ii ，考察每一個a ∈Σ，I i a = f ( I i ， a) 特別地如果Ii中某個狀態Iij不接受a，則另f(Iij，a)=error。如I i a 中的狀態分別落于P中P 個不同的子集，則子集I i 將被P 個更小的狀態子集I i1 ， I i2 ， #8943;， I i p 所細分。令細分后所得的狀態集合為Pnew；

(5) 刪去狀態集中的所有死狀態和出錯狀態，即得到化簡后的M’。

步驟(3)、(4)與原算法相同。使用改進后的分割算法對例1的DFAM重新進行化簡，顯然化簡得到的M’與原來的M相同，即其本身就是最簡的DFA。

4小結

有窮自動機是詞法分析器的基礎，也是編譯原理課程中講授的重點和難點之一。本文使用簡單的實例分析了目前通用教材中“分割法”進行DFA最小化的問題和漏洞，并提出了一種切實可行的改進算法。本算法在教學和多次實例中證明是可行的，這對于從事該課程教學的教師將是很有裨益的。

參考文獻

[1] 張素琴，呂映芝. 編譯原理(第2版)[M]. 北京:清華大學出版社，2005.

[2] 陳應明，馬俊杰. 編譯原理[M]. 北京:冶金工業出版社，2005.

[3] 何炎祥. 編譯原理[M]. 北京:高等教育出版社，2004.

[4] 胡元義. 編譯原理教程[M]. 西安電子科技大學出版社，2006.

[5] 陳火旺，劉春林. 程序設計語言編譯原理(第3版)[M]. 長沙:國防科技大學出版社，2006.