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

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

關(guān)鍵詞：有窮自動(dòng)機(jī)(FA)；確定有窮自動(dòng)機(jī)(DFA)；最小化

中圖分類號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：B

1引言

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

2DFA最小化理論分析

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

1) DFA的最小化定義：是指構(gòu)造一個(gè)與DFA M等價(jià)且狀態(tài)個(gè)數(shù)最少的DFA M′，即等價(jià)最小DFAM′，有L(M)=L(M′)。

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

也可以定義為，若分別以s和t為始點(diǎn)，到達(dá)終態(tài)所識(shí)別字的字集相等，則稱s和t為等價(jià)狀態(tài)。如圖1，以狀態(tài)6為始點(diǎn)所識(shí)別的字集為b*，而以7為始點(diǎn)所識(shí)別的字集為bb*，即b*，所以6和7狀態(tài)為等價(jià)狀態(tài)。

3) 可區(qū)別狀態(tài)：簡言之，如果DFA M中的兩個(gè)狀態(tài)s、t不等價(jià)，則稱s和t是可區(qū)別狀態(tài)。即：以s和t為始點(diǎn)，到達(dá)終態(tài)所識(shí)別字的字集不相等。

DFA M化簡時(shí)的可區(qū)別狀態(tài)可分為以下三種情形：

●非終態(tài)和終態(tài)是可區(qū)別的。因?yàn)?，終態(tài)識(shí)別的字集中一定有ε字而DFA M中的非初態(tài)識(shí)別的字集中不可能有ε字。

●對(duì)同一個(gè)字w，s和t兩個(gè)狀態(tài)，一個(gè)到達(dá)終態(tài)，另一個(gè)到達(dá)非終態(tài)，則s和t可區(qū)別。如狀態(tài)1和狀態(tài)3是可區(qū)別的，因?yàn)闋顟B(tài)3遇b字符而到達(dá)終態(tài)6，即能識(shí)別字b，而狀態(tài)1遇b字符而到達(dá)非終態(tài)2，即能識(shí)別以b開頭的部分字，但不能識(shí)別b字。

●s和t兩個(gè)狀態(tài)，一個(gè)有a字符后繼(a∈Σ)，另一個(gè)無a字符后繼，則s和t可區(qū)別。如狀態(tài)2和狀態(tài)5是可區(qū)別的，因?yàn)闋顟B(tài)2有b字符后繼，能識(shí)別以b開頭的部分字，而狀態(tài)5沒有b字符后繼，不可識(shí)別以b開頭的任何字。

3上述概念中，等價(jià)狀態(tài)和可區(qū)別狀態(tài)是DFA最小化的兩個(gè)重要依據(jù)。

3DFA最小化求解算法改進(jìn)

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

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

3.1DFA狀態(tài)轉(zhuǎn)換矩陣的擴(kuò)展

一個(gè)DFA可以表示成一張狀態(tài)轉(zhuǎn)換矩陣。上圖DFA的狀態(tài)轉(zhuǎn)換矩陣如下表1。其 中的許多oslash;元素，表示當(dāng)前狀態(tài)沒有以對(duì)應(yīng)字符為弧的后繼狀態(tài)。按照此轉(zhuǎn)換矩陣，由某一狀態(tài)集求其對(duì)應(yīng)字符的后繼狀態(tài)集是很方便的，例如I={1，2，3，4，5}，其對(duì)應(yīng)字符的后繼狀態(tài)集為I ={1，2，3，4，5}a={3，4， oslash;}，I={1，2，3，4，5}b={2，6，7，oslash;}。

通常在教科書上，初始劃分一般分為兩個(gè)子集：終態(tài)組和非終態(tài)組。然后對(duì)形成的每個(gè)子集再進(jìn)一步劃分。但對(duì)后繼狀態(tài)集中的{oslash;}算法要特殊處理，因?yàn)樗粚儆谌魏我褎澐肿蛹，F(xiàn)用一種通用算法解決DFA化簡過程中的所有情形：設(shè)想在DFA M狀態(tài)轉(zhuǎn)換中有一個(gè)出錯(cuò)狀態(tài)e，該狀態(tài)為非終止?fàn)顟B(tài)，對(duì)于每個(gè)狀態(tài)，若沒有對(duì)應(yīng)字符為弧的后繼狀態(tài)，均引一條弧到達(dá)出錯(cuò)狀態(tài)e，并在弧上標(biāo)注對(duì)應(yīng)字符。擴(kuò)展后的DFA M如圖2所示，其所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如表2。

3.2 DFA最小化求解算法

依據(jù)可區(qū)別狀態(tài)的定義，可知出錯(cuò)狀態(tài){e}可區(qū)別于終態(tài)集和非終態(tài)集，因?yàn)槌鲥e(cuò)狀態(tài)e識(shí)別的字集為空集。因此，可以將初始劃分為三個(gè)狀態(tài)集(或子集)。改進(jìn)的DFA最小化算法如下：

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

（1）(1) 構(gòu)造狀態(tài)的初始化劃分∏：

終態(tài)kt、非終態(tài)K-kt、、出錯(cuò)狀態(tài)e 三個(gè)子集

（2）(2) 對(duì)∏施用過程PP構(gòu)造新劃分∏_new

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

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

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

(5) 刪除其他等價(jià)狀態(tài)和出錯(cuò)狀態(tài)。

過程PP：構(gòu)造新的劃分∏_new

① 對(duì)∏每一個(gè)狀態(tài)集G進(jìn)行下述工作：

將G劃分為子集。G的兩個(gè)狀態(tài)s和t分在同一子集的充要條件是：對(duì)所有的輸入符號(hào)a，狀態(tài)s和t的a轉(zhuǎn)換都是∏的同一子集中的狀態(tài)。

② 形成的所有子集成為∏_new的狀態(tài)子集。

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

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

現(xiàn)在觀察第一個(gè)子集{1，2，3，4，5}，在讀入輸入符號(hào)a后，狀態(tài)1、2和5分別轉(zhuǎn)換為第一個(gè)子集中所含的狀態(tài)3和4，而3和4分別轉(zhuǎn)換為第三個(gè)子集中所含的狀態(tài)e，這就意味著{1，2，5}中的狀態(tài)和{3，4}中的任何狀態(tài)在讀入a后到達(dá)了不等價(jià)的狀態(tài)，因此{(lán)1，2，5}中的任何狀態(tài)與{3，4}中的任何狀態(tài)都是可區(qū)別的，因此得到了新的劃分P1如下：

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

下面試圖在P1中尋找一個(gè)子集和一個(gè)輸入符號(hào)使得這個(gè)子集中的狀態(tài)可區(qū)別，P1中的子集{1，2，5}對(duì)應(yīng)輸入符號(hào)b將其再分割，而得到劃分P2=({1，2}，{3，4}，{5}，{6，7}，{e})。

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

4 結(jié)束語

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

參考文獻(xiàn)

[1] 張幸兒. 編譯程序構(gòu)造實(shí)踐[M]. 北京:科學(xué)出版社，2005.

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

[3] 馮雁. 編譯原理與技術(shù)[M]. 浙江大學(xué)出版社，2003.

[4] 劉堅(jiān). 編譯原理基礎(chǔ)[M]. 西安電子科技大學(xué)出版社，2002.

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