基于等價關(guān)系的有窮自動機(jī)最小化方法

摘要:主要介紹了有窮自動機(jī)的基礎(chǔ)知識，研究了有窮自動機(jī)的等價性，并在確定型有窮自動機(jī)的狀態(tài)集上引入等價關(guān)系，給出了自動機(jī)的最小化過程。利用等價歸并算法，可以將某一給定的確定型有窮自動機(jī)狀態(tài)集上的等價狀態(tài)歸并掉，生成與其等價的最小化的確定型有窮自動機(jī)。

關(guān)鍵詞:有窮自動機(jī);狀態(tài)轉(zhuǎn)換圖;等價關(guān)系;確定型有窮自動機(jī);最小化

中圖分類號:TP312文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)25-7273-01

Finite Automata Minimization Based on Equivalence Relation

MA Zi-rui

(School of Mathematics and Computer Science， Ningxia University， Yinchuan 750021， China)

Abstract: The paper introduce the foundation knowledge of finite automata and research the equivalence of finite automata. We import equivalence relation in the set of state of DFA and give the procedure of minimum automata. Using the equivalence merger algorithm， we can merge the equivalent states in the set of the automaton’s states and then get the minimized automaton which is equivalent to the original automaton.

Key words: finite automata; state transform figure; equivalence relation; DFA; minimization

有窮自動機(jī)是計算機(jī)軟、硬件研究的重要基礎(chǔ)理論，它在軟件設(shè)計中的應(yīng)用，為設(shè)計者提供了一種新的解決問題的思想和方法[1]。它具有任意有限數(shù)量的內(nèi)部格局或狀態(tài)，用此來記憶過去輸入的有關(guān)信息，根據(jù)當(dāng)前的輸入可確定下一步的狀態(tài)和行為。一個有窮自動機(jī)等價于一個狀態(tài)轉(zhuǎn)換圖。這樣得到的狀態(tài)轉(zhuǎn)換圖可以應(yīng)用有窮自動機(jī)的有關(guān)定理和算法進(jìn)行等價變換、約簡，然后用程序?qū)崿F(xiàn)。由于狀態(tài)轉(zhuǎn)換圖與程序有一定的對應(yīng)關(guān)系，所以使得程序設(shè)計比較規(guī)范化，從而高效的完成了軟件設(shè)計工作。

1 有窮自動機(jī)

給定有限集Σ是一個字母表，Σ*是字母表Σ上有窮符號串構(gòu)成的集合，ε表示空串，串w的長度表示成|w|。Σ上的語言是Σ*的子集，Σ上的正則表達(dá)式可以是Φ，ε或a∈Σ或使用以下規(guī)則的有限次的組合:給兩個正則表達(dá)式α與β，并α+β，差α-β，星運算α*也是正則表達(dá)式。正則表達(dá)式用α或R表示L(α)表示定義在正則表達(dá)式α上的語言[2-3]。

定義1一個有窮自動機(jī)M是一個五元組M=(Q，Σ，δ，q0，F(xiàn))，其中:

l) Q是一個有窮的狀態(tài)集合;

2) Σ是一個有窮的輸入符號集合;

3) δ?哿Q×(Σ∪{ε})×Q是轉(zhuǎn)移函數(shù)，以一個狀態(tài)和一個輸入符號作為變量，返回狀態(tài);

4) q0∈Q是一個初始狀態(tài);

5) F?哿Q是一個終結(jié)狀態(tài)集;

定義2如果δ:Q×Σ→Q，稱自動機(jī)M是確定型有窮自動機(jī)(DFA)。如果δ:Q×Σ×Q，稱自動機(jī)M是非確定型有窮自動機(jī)(NFA)。如果在δ上沒有限制，稱自動機(jī)M是帶ε轉(zhuǎn)移的非確定型有窮自動機(jī)(ε-NFA)。

2 等價性

在研究有窮自動機(jī)與正則表達(dá)式的關(guān)系時，一般引入狀態(tài)轉(zhuǎn)換圖概念，并擴(kuò)充這一概念，使圖中每條邊標(biāo)記為字母表Σ上的字符串或空字ε，稱擴(kuò)展的轉(zhuǎn)換圖，任一擴(kuò)展的轉(zhuǎn)換圖都可轉(zhuǎn)換成等價的ε-自動機(jī)，ε-自動機(jī)是一種包含空字ε的特殊的自動機(jī)。任意一個自動機(jī)都可轉(zhuǎn)換為等價的確定有窮自動機(jī)DFA，而確定有窮自動機(jī)DFA與正則集之間存在等價關(guān)系，即:假定V=L(R)，R是正則集V相對應(yīng)的正則表達(dá)式。Σ上的一個字集V?奐Σ*是正則的充分必要條件，是存在Σ上的確定有限自動機(jī)DFA M使得:V=L(M)。

對于任一給定的確定有窮自動機(jī)DFA M，存在一個正則表達(dá)式R，使得L(M)=L(R)，反之亦然[2-4]。

3 確定型有窮自動機(jī)的最小化

有窮自動機(jī)的最小化是一個十分重要的問題。這里所說的最小化是指在等價的前提下，對有窮自動機(jī)進(jìn)行轉(zhuǎn)換，使得經(jīng)轉(zhuǎn)換所得到的有窮自動機(jī)狀態(tài)結(jié)點最少，但它仍然與原來有窮自動機(jī)等價。

3.1 最小化過程

M=(Q，Σ，δ，q0，F(xiàn))是一個有窮自動機(jī)。M的狀態(tài)轉(zhuǎn)移圖如圖1所示。

為了最小化M，考慮狀態(tài)A與G，從圖1上可以看到:δ*(A，0)={B}，δ*(G，0)={G}，δ*(A，01)={C}∈F，δ* (G，01)=E?埸F，證明A與G可區(qū)分的，即A與G不是等價的。相反，考慮狀態(tài)A與E，從圖1上可以看到:δ*(A，00)={G}，δ*(E，00)={G}，δ*(A，01)={C}，δ* (E，01)={C}，以0開頭的串都能將A，E帶到同一狀態(tài)，且δ*(A，10)={C}，δ* (E，10)={C}，δ*(A，11)={G}，δ* (E，11)={G}，以1開頭的串都能將A，E帶到同一狀態(tài)，足以證明A與E是不可區(qū)分的，即A與E是等價的[5-6]。這樣，據(jù)同樣的算法來求出可區(qū)分狀態(tài)對。最后，可知(A，E)(H，B)(F，D)具有等價關(guān)系。于是形成一個等價類劃分[A，E][H，B][F，D][C][G]。從而得到圖1經(jīng)過最小化的自動機(jī)M’如圖2所示。

3.2 最小化算法

歸并等價狀態(tài)的DFA最小化算法描述如下:

1) 通過等價關(guān)系≈r，找出所有等價狀態(tài)對;

2) 通過1)把狀態(tài)集Q劃分成互相等價的狀態(tài)的塊。此時，塊中所含的狀態(tài)是互相等價的，不同塊中的狀態(tài)是可互相區(qū)別的[7-8];

3) 用塊作為狀態(tài)來構(gòu)造最小化自動機(jī)。

4 結(jié)束語

有窮自動理論給出了一類計算模型，這種模型在計算機(jī)科學(xué)的若干應(yīng)用領(lǐng)域都有著重要的作用。確定型有窮自動機(jī)最小化的關(guān)鍵是在其狀態(tài)集上引入等價關(guān)系，利用等價性，右同余求出狀態(tài)集中所有的等價類來實現(xiàn)自動機(jī)的最小化。一般來說，自動機(jī)的狀態(tài)結(jié)點越少，意味著越節(jié)省軟件和硬件資源，實現(xiàn)它的程序也越簡練。

參考文獻(xiàn):

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，1997.

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

[3] Aho A V，Sethi R，Ullman J D.編譯原理[M].李建中，姜守旭，譯.北京:機(jī)械工業(yè)出版社，2004.

[4] 耿素云.集合論與圖論[M].北京:北京大學(xué)出版社，2000.

[5] 丁春欣.有限自動機(jī)的最小化[J]，高等理科學(xué)刊，2000，20(3):8-10.

[6] 徐江.對確定有限自動機(jī)最小化算法的改進(jìn)[J].桂林航天工業(yè)高等專科學(xué)校學(xué)報，2005(4):14-16.

[7] 宿云.確定型有窮自動機(jī)最小化算法的三點說明[J].信息技術(shù)，2005，34(6):41-52.

[8] 戚國正，楊崇耀.關(guān)于概率自動機(jī)的等價性與極小化問題[J].貴州科學(xué)，1994，12(1):8-11.