摘要 本文對自動機(jī)理論的研究主要是兩個方面：自動機(jī)的極小化和極小化的時間 復(fù)雜性。 在自動機(jī)的狀態(tài)集合上定義等價關(guān)系，引入等價類，將等價的狀態(tài)合并成一 個狀態(tài)，生成新的狀態(tài)數(shù)較小的自動機(jī)。新生成的自動機(jī)與原自動機(jī)識別的語言 不變，也就是說它們是等價的。這就是樹圖分割法的思想。利用樹圖分割法可以 進(jìn)行確定型有窮自動機(jī)的極小化。 本文的重點內(nèi)容是構(gòu)造了一類非確定型有窮自動機(jī)，即連接型有窮自動機(jī)。 這類有窮自動機(jī)是由兩臺確定型有窮自動機(jī)連接而成的。利用兩臺確定型有窮自 動機(jī)狀態(tài)集合上的等價關(guān)系可以構(gòu)造出連接型有窮自動機(jī)狀態(tài)集合上的等價關(guān) 系。這類非確定型有窮自動機(jī)也可以利用樹圖分割法來極小化。還可以得到連接 后再極小化的自動機(jī)的狀態(tài)數(shù)不大于極小化后再連接的自動機(jī)的狀態(tài)數(shù)。 非確定型有窮自動機(jī)的情況比較復(fù)雜。往往比較大的有窮自動機(jī)沒有等價狀 態(tài)，但將其中某兩個或者幾個狀態(tài)進(jìn)行合并并不改變它們的語言。本文給出了非 確定型有窮自動機(jī)狀態(tài)合并的條件。找到了非確定型有窮自動機(jī)極小化狀態(tài)的臨 界條件。 自動機(jī)極小化的時間復(fù)雜性，有效的驗證了極小化算法是否有效。一般地， 多項式時間內(nèi)能完成的就認(rèn)為該算法是有效的。確定型有窮自動機(jī)和連接型有窮 自動機(jī)利用樹圖分割法進(jìn)行極小化，它們都在狀態(tài)的三次方時間內(nèi)就可以完成。 本文的最后給出了非確定型有窮自動機(jī)極小化算法。 關(guān)鍵詞：連接型有窮自動機(jī)等價關(guān)系不可區(qū)分狀態(tài) 時間復(fù)雜性樹圖分割法臨界條件 中圖分類號：t p 3 0 1 1 3 文獻(xiàn)標(biāo)識碼：h a b s t r a c t t h er e s e a r c ho ft h ea u t o m a t i o nt h e o r ym a i n l yi n c l u d e st w oa s p e c t s ：o n ei s m i n i m i z a t i o no fa u t o m a t o na n dt h eo t h e ri si t st i m ec o m p l e x i t y e q u i v a l e n tr e l a t i o n s a r ed e f i n i t e di nt h es e to ft h ea u t o m a t i o n ss t a t e sa n d e q u i v a l e n tc l a s s e sw i l lb ei n t r o d u c t e d t h e nt h ee q u i v a l e n ts t a t e sw i l lb em e r g e di n t o o n es t a t e ，s ot h en e wg e n e r a t i o no fa u t o m a t i o nw i l lb es m a l l e r t h el a n g u a g et h a tt h e n e wg e n e r a t i o no fa u t o m a t i o na c c e p t si st h es a m ea st h el a n g u a g et h a tt h eo r i g i n a l a u t o m a t o na c c e p t s t h a ti st os a y ，t h e ya r ee q u i v a l e n t t h i si st h et r e es e g r e g a t e d m e t h o d t r e es e g r e g a t e dm e t h o dc a nb eu s e dt om i n i m i z ed e t e r m i n i s t i ct - m i t e a u t o m a t i o n ( d f a ) ak i n do fn o n d e t e r m i n i s t i cf i n i t ea u t o m a t i o n ( n f a ) i st h ef o c u so ft h i sp a p e r t h a ti sc o n n e c t i n gn f a s u c hn f ai sd e t e r m i n e db yt h et w o - d f a u s i n ge q u i v a l e n t r e l a t i o n so ft w o d f a ss t a t ec a nc o n s t r u c te q u i v a l e n tr e l a t i o no fc o n n e c t i n gn f a s t h es t a t e s u c hn f ac a l la l s ou s et r e es e g r e g a t e dm e t h o dt om i n i m i z e c o n c l u s i o n s c a nb eg o tt h a tt h en u m b e ro ft h em i n i m i z i n gc o n n e c t i n ga u t o m a t i o n ss t a t e si sn o t m o r et h a nt h en u m b e ro ft h e c o n n e c t i n gm i n i m i z i n ga u t o m a t i o n ss t a t e s n f ai sm o r ec o m p l i c a t e d ab i gn f ai so f t e nn oe q u i v a l e n ts t a t e s ，b u tm e r g i n g t w oo rs e v e r a ls t a t e sd o n tc h a n g ei t sl a n g u a g e i nt h i sp a p e rc o n d i t i o no fm e r g i n g s t a t e si sg i v e na n dt h en u m b e ro fm i n i m u ma u t o m a t i o n ss t a t e si sf o u n d t h et i m ec o m p l e x i t yo fm i n i m i z i n ga u t o m a t i o ni sv e r ye f f e c t i v et ot e s ta l g o r i t h m i ng e n e r a l ，t h ea l g o r i t h mw h i c hc a nb ec o m p l e t e di np o l y n o m i a lt i m ei se f f e c t i v e u s i n go ft r e es e g r e g a t e dm e t h o d , d f aa n dc o n n e c t i n gn f a c a nb em i n i m i z e di n c u b i ct i m e f i n a l l yt h ea l g o r i t h mo fm i n i m i z i n gn f ai sp r e s e n t e di nt h i sp a p e r k e yw o r d s ：c o n n e c t i n gn f a e q u i v a l e n tr e l a t i o n u n d i s t i n g u i s h e ds t a t e t i m ec o m p l e x i t y t r e es e g r e g a t e dm e t h o d c r i t i c a lc o n d i t i o n 4 原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下， 獨立進(jìn)行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本 論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的科研成果。 對本文的研究在做出重要貢獻(xiàn)的個人和集體，均已在文中以明確 方式標(biāo)明。本人完全意識到本聲明的法律責(zé)任由本人承擔(dān)。 論文作者簽名： 奎秘 日 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人完全了解貴州大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，同 意學(xué)校保留或向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子 版，允許論文被查閱和借閱；本人授權(quán)貴州大學(xué)可以將本學(xué)位論 文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、 縮印或其他復(fù)制手段保存論文和匯編本學(xué)位論文。 ( 保密論文在解密后應(yīng)遵守此規(guī)定) 論文作者簽名：獬導(dǎo)師簽名： 日期：21 q 垃旦 第一章前言 1 1 研究背景 自動機(jī)理論是研究抽象計算的裝置或“機(jī)器 。在2 0 世紀(jì)3 0 年代計算機(jī)出 現(xiàn)之前，圖靈研究過一種抽象機(jī)器，這種機(jī)器具備了今天計算機(jī)的所有能力。圖 靈的目是精確地描述一條界線，這條界線區(qū)分計算機(jī)能做什么和不能做什么。圖 靈的結(jié)論不僅適用于抽象的圖靈機(jī)，也適用于今天的真實計算機(jī)( 2 5 j o l m e h o p c r o f l ，e t c 2 0 0 4 ) 。 在2 0 世紀(jì)4 0 和5 0 年代，一些科學(xué)家開始研究有窮自動機(jī)，有窮自動機(jī)理 論是h u f f m a n 、m o o r e 等人開創(chuàng)的。它給出了一類計算模型，這種模型在計算機(jī) 科學(xué)的若干應(yīng)用領(lǐng)域都有著重要的作用( 3 0 m i c h a e ls i p s e r , 2 0 0 0 ) 。有窮自動機(jī) 理論的發(fā)展對今天計算機(jī)科學(xué)的影響是深遠(yuǎn)的，經(jīng)過幾十年的發(fā)展，自動機(jī)理論 已成為計算機(jī)科學(xué)中的一個重要分支，并應(yīng)用于計算機(jī)科學(xué)的許多領(lǐng)域，如編譯 程序構(gòu)造、文本處理、結(jié)構(gòu)型數(shù)據(jù)翻譯以及開關(guān)線路設(shè)計等，它是計算機(jī)軟件、 硬件研究的重要基礎(chǔ)理論( 1 9 c c a m p e a n u ，e t c 2 0 0 1 ) 。 正規(guī)式理論是由k l 爸爸n e 于1 9 5 6 年提出的，正則表達(dá)式與有窮自動機(jī)是根本 不同的，但它們表示完全相同的語言正則語言。正則表達(dá)式的最重要之處是 在有窮自動機(jī)中的應(yīng)用( 3 0 m i c h a e ls i p s e r , 2 0 0 0 ) 。由于從正則表達(dá)式得到的 d f a 的大小呈指數(shù)形式且最小的n f a 是很難得到的。因此，是否考慮用其它的 一些方法來尋求最小的自動機(jī)。這種觀點得到的自動機(jī)不一定是最小的，但可以 “適度”的小而且可以在很高的效率下被構(gòu)造。研究自動機(jī)的專家完成了從正則 表達(dá)式構(gòu)造典型的帶空轉(zhuǎn)移的( 一n f a ) 的算法，而且得到的n f a 的大小呈線 形( 2 6 k t h o m p s o n ，1 9 6 8 ) ，s i p p u 與s o i s a l o n s o i n i n e n 還改進(jìn)了t h o m p s o n 的算 法使得構(gòu)造的e n f a 更小。但是，不帶s 轉(zhuǎn)移的n f a 的情形是比較困難的。鑒 于這種情況，由另外一些專家 r m c n a u g h t o n 。y a m a d a ( 3 2 r m c n a u g h t o n ，h y a m a d a ，1 9 6 0 ) 與v m g l u s h k o v ( 3 6 v m g l u s h k o v , 1 9 6 1 ) 尋找 到了一個好的用來構(gòu)造較小的n f a 的算法，是“位置自動機(jī) ，v a n t i m i r o v ( 3 5 v a n t i m i r o v , 1 9 9 6 ) 在位置自動機(jī)的基礎(chǔ)上又尋找了一個較好的算法，是“基于偏 導(dǎo)的自動機(jī)，l i l i e ( 2 9 l i l i e ，s y u ，2 0 0 3 ) 也在位置自動機(jī)基礎(chǔ)上有尋找了一個 更好的算法，是“序自動機(jī)”，后者所得到的自動機(jī)是很小的。 5 1 2 研究的主要內(nèi)容及意義 隨著計算機(jī)控制技術(shù)的廣泛應(yīng)用，軟件設(shè)計越來越復(fù)雜，要求越來越高，其 實時性、并發(fā)性、交互性以及友好性等都難以用順序的靜態(tài)的程序來描述和實現(xiàn)。 有窮自動機(jī)在軟件設(shè)計中的應(yīng)用，為設(shè)計者提供了一種新的解決問題的思想和方 法。一個有窮自動機(jī)等價于一個狀態(tài)轉(zhuǎn)換圖。這樣得到的狀態(tài)轉(zhuǎn)換圖可以用有窮 自動機(jī)的有關(guān)理論和算法進(jìn)行等價變換、約簡，然后用程序?qū)崿F(xiàn)。由于狀態(tài)轉(zhuǎn)換 圖與程序有一定的對應(yīng)關(guān)系，所以使得程序比較規(guī)范化，從而高效的完成了軟件 設(shè)計工作，因此有窮自動機(jī)的化簡成為重要的研究課題。 本文對于有窮自動機(jī)的研究，主要基于兩個方面：一是對有窮自動機(jī)的極小 化；二是極小化的時間復(fù)雜性。 在等價的前提下，自動機(jī)的狀態(tài)越少，意味著越節(jié)省軟件和硬件資源。有窮 自動機(jī)的極小化是指將自動機(jī)的狀態(tài)集劃分成一些不相交的子集，使得任何兩個 不同的子集中的狀態(tài)都是可區(qū)分的，而同一子集中的任何兩個狀態(tài)都是等價的。 本文引入樹圖分割法，搜索所有不可區(qū)分到的狀態(tài)，將不可區(qū)分的狀態(tài)對進(jìn)行合 并，就實現(xiàn)了自動機(jī)的極小化。 本文還找到了非確定有窮自動機(jī)狀態(tài)合并的條件以及極小化的狀態(tài)臨界條 件。最后給出了一般非確定型有窮自動機(jī)極小化算法。 1 3 本文的結(jié)構(gòu)安排及主要工作 本文共分為五章，總共十個部分，結(jié)構(gòu)如下： 第一章：前言。主要介紹了本論文的研究背景及研究意義； 第二章：有窮自動機(jī)基本理論。主要介紹自動機(jī)的基本定義、定理； 第三章：確定型有窮自動機(jī)的極小化； 第四章：連接型有窮自動機(jī)的極小化； 第五章：非確定型有窮自動機(jī)的極小化； 另外，本文還包括全文總結(jié)及進(jìn)一步的工作、致謝、參考文獻(xiàn)、附錄以及原創(chuàng)性 聲明五個部分。 6 第二章有窮自動機(jī)基本理論 2 1 引言 有窮自動機(jī)理論是描述詞法規(guī)則的基本理論。在實際應(yīng)用中，有窮自動機(jī)是 關(guān)于存儲極其有限的計算機(jī)的很好的模型，它有一組狀態(tài)及其控制，響應(yīng)外部“輸 入 ，“控制 從狀態(tài)移動到狀態(tài)。各類有窮自動機(jī)之間的關(guān)鍵區(qū)別之一，在于 控制究竟是“確定的 還是“非確定的”，前者意味著在任何時刻自動機(jī)不能處 在一種以上狀態(tài)中，后者意味著能同時處在幾種狀態(tài)中。我們知道，增加非確定 性并不能定義出任何不能用確定型有窮自動機(jī)來定義的語言，但是用非確定型有 窮自動機(jī)來描述應(yīng)用卻具有很高的效率。事實上，非確定性允許用較高層語言來 “設(shè)計問題的解( 2 8 l i l i e ，s y u ，2 0 0 2 ) 。通常我們可以通過算法將非確定型有 窮自動機(jī)轉(zhuǎn)化為確定型有窮自動機(jī)，然后在常規(guī)計算上“執(zhí)行 。 2 2 確定型有窮自動機(jī)基本概念 定義2 1 確定型有窮自動機(jī)d f a 是一個五元組m 一( q ，6 ，q o ，f ) ，其中： ( 1 ) q 是一個有窮集合，叫做狀態(tài)集。 ( 2 )是一個有窮集合，叫做字母表。 ( 3 ) 6 ：q z 呻q 是轉(zhuǎn)移函數(shù)。 ( 4 ) q o q 是起始狀態(tài)。 ( 5 ) f q 是接受狀態(tài)集。 通常，我們對字符a 和字符串，我們可以寫作 ( q i ，a g o ) 一( 6 ，口) ，) ，這里的符號一指一步變遷。m 接受一個在上的字符 串，可以表示為：對于某個廠f ，( 留。，) _ ( 廠，允) 這里九表示空串，呻+ 表示 有限次變遷。 定義2 2 ( 轉(zhuǎn)移函數(shù)的擴(kuò)展) 設(shè)m ；( q ，6 ，q o ，f ) 一臺確定型有窮自動機(jī)， 定義6 如下： ( 1 ) 6 + 國，a ) = q( 狀態(tài)g 下不讀任何輸入，就還處在g 中) ( 2 ) 假設(shè)一x r ，也就是說，a 是0 3 的結(jié)尾符號，x 是包含除結(jié)尾符號外的 7 所有符號串，6 國，) = 6 ( 6 ( 鳥，x ) ，a ) 。 此定義的思想是，為了計算6 國，) ，首先計算6 固，z ) ，6 + ( g ，z ) 計算完后所處 的狀態(tài)是自動機(jī)在處理的結(jié)尾符號外的所有符號之后所處的狀態(tài)。假設(shè)這個狀 態(tài)是p ，也就是說，6 。( g ，x ) = p ，那么6 0 ，) 就是從狀態(tài)p 再輸k a ( 的 結(jié)尾符號) 上轉(zhuǎn)移所得到的狀態(tài)，即有6 ( g ，c o ) = 6 0 ，a ) 。 定義2 3 ( d f a 接受的語言)設(shè)mt ( q ，z ，6 ，g o ，) 是臺確定型有窮自 動機(jī)，m 所接受的語言記為l ( m ) ，定義為：l ( m ) 一伽i6 。，) ，】- 也就是 說，語言l ( m ) 是讓初始狀態(tài)吼通向接受狀態(tài)之一的串的集合( 2 5 j o h n e h o p c r o f t ，e t c 2 0 0 4 ) 。 一臺機(jī)器可能接受若干字符串，但是它永遠(yuǎn)只能識別一個語言。若一個語 言被一臺確定型有窮自動機(jī)識別，則稱這個語言為正則語言。 例2 4 圖2 1有窮自動機(jī)旭 = 【c ol 至少含有一個1 或者在最后的l 后面有偶數(shù)個o 】- l ( m 。) = l ，即稱m 。識別l 或者m 。接受l 。若機(jī)器不接受任何字符串，那么它仍 然識別一個語言，即空語言。 定義2 5 ( 狀態(tài)軌跡) 設(shè)m ；( q ，6 ，q o ，) 為一臺確定型有窮自動機(jī)( d f a ) ， 由6 定義函數(shù)6 ：q 宰呻q 如下： 6 t ( g ，) 一q ，6 ( q ，a x ) 一6 ( 6 ( g ，口) ，x ) 其中三是指上的有窮符號串構(gòu)成的集合，稱串x 將狀態(tài)留帶到狀態(tài)6 ( g ，z ) 。對 于x a l a 2 口3 a 。稱狀態(tài)序列口o ，q 1 ，日2 吼為串z 將留。帶到狀態(tài)6 + ( ，z ) 的 狀態(tài)軌跡，其中4t6 ( 黿o ，a l a 2 口3 a 。) 1s is ，l 記：q 國，石) = _ 【吼，9 1 ，留2 吼 。 定義2 6 設(shè)m 一( a ，6 ，q o ，f ) 為一臺確定型有窮自動機(jī)，在q 上引入二元 關(guān)系r ：v p ，q e a ， r 營( 覘) ( 6 0 ，x ) f 營6 ( g ，z ) ，) 。容易驗 證：尺滿足自反性，對稱性和傳遞性，所以尺是q 上的一個等價關(guān)系。對于 8 m 坳，g q ， r ，稱狀態(tài)p ，q 不可區(qū)分的，即表示p ，黿等價。若j + ， 使6 + 0 ，) 與6 ，c o ) 中的一個到達(dá)接受狀態(tài)的而另一個到達(dá)非接受狀態(tài)，稱狀 態(tài)p ，q 可區(qū)分，& 為區(qū)分p ，q 的證據(jù)。 兩個狀態(tài)s 和r 等價的條件是( 1 3 韓光輝，1 9 9 8 ； 1 4 韓光輝2 0 0 5 ) ： ( 1 )一致性條件：狀態(tài)s 和r 必須同時為可接受狀態(tài)或不可接受狀態(tài)。 ( 2 ) 蔓延條件：對于所有輸入符號狀態(tài)s 和r 必須轉(zhuǎn)換到等價的狀態(tài)里。 也就是說，兩個狀態(tài)若相等應(yīng)滿足：在同樣輸入的作用下都有相同的輸出；在同 樣的輸入條件下其相應(yīng)的次態(tài)應(yīng)彼此等價。這可能存在三種情況：對應(yīng)次態(tài)相同； 其次態(tài)就是兩個現(xiàn)態(tài)本身；其次態(tài)是彼此等價的。 定理2 7 設(shè)m = ( q ，6 ，q 。，f ) 是一臺確定型有窮自動機(jī)，在狀態(tài)q 上，若p ，口 是等價的，q ，r 是等價的，則狀態(tài)p ，是等價。 證明：設(shè)q 上的等價關(guān)系為尺， ( p ，口) 尺辛( v x x + ) ( 6 p ，z ) f 營6 ( 日，x ) e f ) ( 口，r ) r 號( v x x ) ( 6 ( g ，z ) ，尊6 ( r ，x ) f ) 則有：( p ，) 尺凈( v x x ) ( 6 ( p ，z ) f 營6 r ，x ) ，) 所以p ，是等價的。 定義2 8 ( 等價類自動機(jī)) 設(shè)m 一( q ，6 ，q o ，f ) 為一臺確定型有窮自動機(jī) ( d f a ) ，借助等價關(guān)系只，取等價類【p 】i 佃q ： 耐，我們可以構(gòu)造 一臺m 的等價類自動機(jī)【m 】，【m 】一( q ，6 + ，q 。，) 其中： q = 瞳】1 日q ) ； ：字母表保持不變； 6 ：0 x x 啼q 并且( 1 ) 6 ( 口，) 一q ； ( 2 ) 6 ( 黿，踟) = 6 固，山) ，口) 。6 ( q ，a ) ，其中6 ( 黿，) 一q ； q o 一【q ?！砍跏紶顟B(tài)； f - k 】i g ，) 接受狀態(tài)； 定義2 9 ( 極小化自動機(jī)定義) 設(shè)m - ( q ，6 ，q o ，f ) 為一臺確定型有窮自動 機(jī)( d f a ) ，( m ) = b 。稱m 為接受語言b 的極小化自動機(jī)，如果接受召的任 何自動機(jī)的狀態(tài)數(shù)不低于l q i 。 9 2 3 非確定型有窮自動機(jī)基本概念 定義2 1 0 非確定型有窮自動機(jī)是一個五元組一( q ，6 ，q o ，f ) ，其中， ( 1 ) q 是一個有窮集合，叫做狀態(tài)集； ( 2 ) 是一個有窮集合，叫做字母表； ( 3 ) 6 ：q x x 。_ q 是轉(zhuǎn)移函數(shù)( 這里。- u e ) ； ( 4 ) q 。q 是起始狀態(tài)； ( 5 ) f q 是接受狀態(tài)集。 非確定型有窮自動機(jī)的轉(zhuǎn)移函數(shù)6 是一個以q 中一個狀態(tài)和中一個輸 入符號作為變量并且返回q 的一個子集的函數(shù)。n f a 與d f a 之間的唯一區(qū)別在 于6 的返回值的類型：在n f a 的情況下，返回值是一個狀態(tài)集合，而在d f a 的 情況下返回值是單個狀態(tài)( 1 8 c c a m p e a n u ，e t c 2 0 0 5 ) 。 定義2 1 1 ( 轉(zhuǎn)移函數(shù)的擴(kuò)展) 設(shè)n = ( q ，6 ，q 。，f ) 一臺非確定型有窮自動機(jī)， n f a 的轉(zhuǎn)移函數(shù)6 的擴(kuò)展函數(shù)6 定義如下： 7 ( 1 ) 6 + ( g ，g ) l 幻)( 狀態(tài)目下不讀輸入，就還處在狀態(tài)g 中) ( 2 ) 假設(shè)一x a ，也就是說，a 是緲的結(jié)尾符號，x 是包含除結(jié)尾符 k 號外的所有符號串，若6 ，x ) = 仞t ，p ：既卜柚u 6 ( p t ，口) = “，r 2 ，k ) 那 么6 。( 口，) = “，吃，k 。此定義的思想的實質(zhì)是首先計算6 + ( q ，z ) ，然后遵 循從這些狀態(tài)中任何一個狀態(tài)出發(fā)的帶a 的標(biāo)記的任何轉(zhuǎn)移。 對于非確定型有窮自動機(jī)，在讀的各個字符時，有可能形成對下一個的選 擇序列，并從初始狀態(tài)到達(dá)任何接受狀態(tài)。用的輸入符號的其它選擇、導(dǎo)致非 接受狀態(tài)或者根本不會導(dǎo)致任何狀態(tài)( 即狀態(tài)序列“死亡刀) ，這樣的事實不妨礙 n f a 在總體上接受( 1 1 秦永彬，許道云，2 0 0 6 ) 。 定義2 12 ( 非確定型有窮自動機(jī)狀態(tài)等價) 設(shè)n 一( q ，6 ，q 。，f ) 是一臺非 確定型有窮自動機(jī)，在q 上引入等價關(guān)系r ：若p ，q e q 且v ，有 1 0 6 q ，) nf 乒g 6 + ( g ，) nf 乒f 2 j ，貝0 稱 尺。 定義2 1 3 ( 等價類有窮自動機(jī)) 設(shè)n 一( q ，6 ，q o ，f ) 是一臺非確定型有窮 自動機(jī)，由狀態(tài)集q 上的等價關(guān)系尺所確定的等價類【p 】- 幻q ： 尉， 則的極小化自動機(jī)可表示為： 。 n 孤i 。一( 【p 】：p e q ，6 。i n ，【q ?！浚?【p 】：p f ) ) ( 其中6 。證( 【p 】，a ) 16 0 ，a ) 2 4 帶轉(zhuǎn)移的非確定型有窮自動機(jī)基本概念 現(xiàn)在介紹有窮自動機(jī)的另一種擴(kuò)展。新“特征 允許在空串上的轉(zhuǎn)移。實 際上，允許n f a 沒有收到輸入符號就自動轉(zhuǎn)移，這類自動機(jī)與非確定型有窮自 動機(jī)是一樣的，并不擴(kuò)大有窮自動機(jī)接受的語言類，但是在程序設(shè)計中發(fā)揮了很 大的便利。 帶轉(zhuǎn)移的非確定型有窮自動機(jī)的形式化表示與非確定型有窮自動機(jī)的形 式化表示類似，只是有一點例外的，即轉(zhuǎn)移函數(shù)必須含有在占上轉(zhuǎn)移的信息。形 式化地，把一j 跗表示成札t ( q ，6 。，q o ，f ) ，其中，除6 。外，其它所有的組 成部分都有與n f a 同樣的解釋，而6 。是有下列變量的函數(shù)： ( 1 ) 首先具有狀態(tài)集q 中的一個狀態(tài)； ( 2 ) 其次具有集合u 】中的一個元素，也就是說，要么是輸入符號，要么 是符號，并且要求f 不是字母表中的符號； 閉包順著所有狀態(tài)g 出發(fā)帶標(biāo)記的來轉(zhuǎn)移到達(dá)其它狀態(tài)，然后再順著這些狀 態(tài)發(fā)出的轉(zhuǎn)移，依此類推，最終求出順著箭弧都帶f 標(biāo)記的任何路徑從g 可達(dá) 的每個狀態(tài)，稱為狀態(tài)g 的閉包，記為：e c l o s e ( q ) 。 例2 1 4如圖是一n f a 狀態(tài)圖的一部分。 圖2 2 一n f a 的部分狀態(tài)圖 1 1 從狀態(tài)1 出發(fā)，順著只帶標(biāo)記的路徑有1 呻2 一3 6 ，1 _ 4 。因此 e c l o s e ( 1 ) 一仉2 ，3 ，4 ，6 。 定義2 1 5 ( s n f a 轉(zhuǎn)移函數(shù)6 的擴(kuò)展) 設(shè)e 一朋啊n 一( q ，6 ，q o ，f ) 轉(zhuǎn) 移函數(shù)6 的擴(kuò)展函數(shù)6 。定義如下： 基礎(chǔ)：6 ( g ，) i e c l o s e ( q ) 也就是說，如果這條路徑的標(biāo)記是，則只能順著 從狀態(tài)口出發(fā)帶占標(biāo)記的箭弧，這恰好是e c l o s e 所做的。 歸納：設(shè)形如x a ，其中a 是的結(jié)尾符號。注意a ，a 是不能為，甓。 計算6 ( g ，) 如下： 1 設(shè)6 ( 口，x ) 為 島，p ：，p 。) 。也就是說，這些只是順著標(biāo)記為x 的路徑可達(dá) 的所有狀態(tài)。這條路徑可能以一個或者多個帶f 標(biāo)記的轉(zhuǎn)移來結(jié)尾，也可能 有其它的f 轉(zhuǎn)移。 2 設(shè)u 乞。6 ( p i ，a ) 為饑，r 2 ，k ) 也就是說，順著帶x 標(biāo)記的路徑從q 到達(dá)一些 狀態(tài)，遵循所有帶a 標(biāo)記的從這些狀態(tài)發(fā)出的轉(zhuǎn)移，這些是順著帶甜標(biāo)記的 路徑從口可達(dá)的一些狀態(tài)，順著下面的步驟( 3 ) 中的標(biāo)記的箭弧，從這些 求出其它可達(dá)的狀態(tài)。 3 6 國，) iu 7 ，e c l o s e ( 5 ) 。 定義2 16 ( 一m 啊所接受的語言) 設(shè)i ( q ，6 ，q o ，f ) 是一臺一n f a ，則 一n f an 所接受的語言記為l ( n ) ：l ( ) i 和i6 ( 鳥。，) n f a ) 。 2 5 連接型有窮自動機(jī)基本概念 定義2 1 7 m ，i l a ( q l ，6 ，q o ，e ) ，m ：i ( q 2 ，6 ：，q 。，e ) 是兩臺確定型有窮 自動機(jī)，它們的連接型有窮自動機(jī)：n - m ，。m ：i ( 0 1u q 2 ，6 ，q 。，丘u e ) 是 一臺非確定型有窮自動機(jī)。本文取q 1nq ：一彩進(jìn)行討論。其中6 定義為： 1 2 6 0 ，t o ) = 6 ，p ，) 若pe q , f 1 6 ，0 ，) 都互，一f 且貿(mào)0 ，緲) 茁f 6 ，0 ，c o ) u q o ) 著p 互且( 一或6 7 ( p ，t o ) f ) p ：p ，) ) 若p e q ： 定義2 1 8 設(shè)- m 。m ：i i ( quq 2 ，6 ，q 。，互u f ：) 是一臺連接型的有窮自 動機(jī)，所接受的語言記為l ( ) ，定義為：l o v ) - 枷l6 ( ，) n ( 互u f ：) - 囝) 。 也就是說，語言l ( n ) 是讓初始狀態(tài)q o 通：q 接受狀態(tài)之一的串的集合。 ， 定義2 19 ( 連接關(guān)系) ( 1 0 j 徐江，2 0 0 5 ； 1 2 宿云，2 0 0 5 )連接關(guān)系是將 兩個關(guān)系進(jìn)行笛卡爾積再從笛卡爾積中選擇滿足一定條件的記錄的運(yùn)算。設(shè)選擇 條件為f ( 可以為一個一般的條件表達(dá)式) ，則連接關(guān)系可記為： r o o ，s = piri ( t l ，t 2 ) n ( 瓴尺) n ( 乞e s ) ) f lf o ) ) 。 定義2 2 0 ( 墨，恐) 設(shè)m ，i l m ( q l ，島。q o ，互) ，m 2 ；( q ：，6 ：，留o ，e ) 是兩臺 確定型有窮自動機(jī)，r 和恐分別是q 1 和q 2 上的等價關(guān)系，稱 r o 。，r 2 ， 若滿足p q 1 ，q e q 2 ，且v ，按照定義2 1 1 中所定義的轉(zhuǎn)移函數(shù)6 ，有 6 0 ，) n e 一乃寺爭6 ( g ，) f - ) e g 。 2 6 確定型有窮自動機(jī)與非確定型有窮自動機(jī)的等價性 對于許多語言來說，構(gòu)造n f a 比構(gòu)造更容易，出入意料的是，每一介用某 個n f a 描述的語言也能用某個d f a 來描述。也就是說n f a 好象并不比d f a 識別 的語言多。實際上，確定型有窮自動機(jī)和非確定型有窮自動機(jī)識別相同的語言類。 但是，對于給定的某個語言，描述識別這個語言的n f a 有時比描述識別這個語 言的d f a 更容易得多。 如果兩臺機(jī)器識別相同的語言，則稱它們是等價的。 定理2 2 1 每臺非確定型有窮自動機(jī)都有一臺確定型有窮自動機(jī)與之等價。 設(shè)一個語言被一臺n f a 識別，必須證明存在一臺d f a 也識別這個語言?；?本想法是把n f a 轉(zhuǎn)換成模擬它的d f a 。 證明：設(shè)nt ( q ，6 ，q o ，f ) 是識別語言l 的n f a ，要構(gòu)造一臺d f am 來識 別。在給出完整的構(gòu)造之前，先考慮比較容易的情況，假設(shè)沒有s 箭頭。以 1 3 后再把箭頭考慮進(jìn)來。 下面來構(gòu)造m 一( a ，6 ，口o ，) 1 ) a - p ( q ) m 的每一個狀態(tài)是的一個狀態(tài)子集。p ( q ) 是q 的所有子集 組成的集合； 2 ) 對于r e q 。和口，令6 似，a ) ；幻q i 存在，r ，使得q 5 ( r ，口) 。如 果r 是m 的一個狀態(tài)，則它是的一個狀態(tài)子集。當(dāng)m 在狀態(tài)尺讀符號a 時， 6 ( 尺，a ) 給出a 把尺中的狀態(tài)帶到什么地方。由于每一個狀態(tài)可以轉(zhuǎn)移到一個狀 態(tài)子集，所以取所有這些子集的并a 記為：6 ( 尺，口) ；u 6 ( ，口) ； 3 ) q o 。 吼】，m 開始時所在的狀態(tài)對應(yīng)于只含n 的起始狀態(tài)的集合； 4 ) f t 怛e a lr 包含的一個接受狀態(tài)) ； 如果當(dāng)時的可能狀態(tài)中有一個接受狀態(tài)，則機(jī)器m 接受。 現(xiàn)在來考慮f 箭頭，為此再引入一個記號。對于m 的任意一個狀態(tài)r ，根 據(jù)閉包的定義e c l o s e ( r ) = 臼l 從r 出發(fā)沿著0 個或多個占箭頭可以到達(dá)g 】然 后，我們修改m 的轉(zhuǎn)移函數(shù)，使得在每一步之后，在沿著箭頭可以達(dá)到的所 有狀態(tài)也包含在里面，用e c l o s e ( 5 ( r ，口) ) 代替6 ( ，a ) 能產(chǎn)生這個效果于是 6 ( r ，a ) 一幻e a i 存在r e r ，使得q e e c l o s e ( 5 ( r ，口) ) 】此外還要修改一下膨的 起始狀態(tài)，使得開始時口。把從的起始狀態(tài)出發(fā)沿著箭頭可以達(dá)到的所有狀 態(tài)也要包含近來即 g 。t 改為 g o 卜：e c l o s e ( i q o ?！? 就能產(chǎn)生這個效果。 現(xiàn)在已經(jīng)完成了模擬n f an 的d f am 的構(gòu)造m 的構(gòu)造顯然是正確的， 在計算的每一步，m 進(jìn)入的狀態(tài)明顯地對應(yīng)于此時可能處于的狀態(tài)子集。 例2 2 2 一臺非確定型有窮自動機(jī)，它的初始狀態(tài)為q o ，接受狀態(tài)為q 2 我們 可以認(rèn)為，只要自動機(jī)還沒有“猜測 到結(jié)尾的0 1 ，那么自動機(jī)就一直處在鳥o ， o j 一 一 圖2 3 接受所有以0 1 結(jié)尾的串n f a 1 4 可能出現(xiàn)這樣的情況：即使下一個符號是o ，這個符號也不是結(jié)尾0 1 的開始。 因此，狀態(tài)q 0 在0 和1 上都可以轉(zhuǎn)移到自身。但如果下一個符號是0 ，這個n f a 也猜測到了結(jié)尾0 1 串開始了，因此，這時自動機(jī)從狀態(tài)開始在符號o 的作用 下到達(dá)狀態(tài)9 1 ，吼在符號1 的作用下到達(dá)終結(jié)狀態(tài)口：。注意，有兩個從q 。出發(fā) 帶o 標(biāo)記的箭弧，n f a 可以選擇進(jìn)入吼或者吼，實際上都進(jìn)入。沒有從q 。出發(fā) 帶。標(biāo)記的箭弧，在g ；狀態(tài)下，如果該n f a 驗證的下一個符號是l ，則該自動機(jī) 就會進(jìn)入狀態(tài)g ：。口：是該自動機(jī)的終結(jié)狀態(tài)，在該n f a 中，根本沒有從q ：出發(fā) 的箭。在這種情況下，該n f a 中存在的與這些狀態(tài)相對應(yīng)的線路就終止了，但 其它的線路還可繼續(xù)存在。在某個d f a 中，對每一個輸入符號恰好有一個箭弧 離開每一個狀態(tài)。則與n f an 等價的d f am 的轉(zhuǎn)換圖為： 例2 2 3 - - - - 圖2 4 例2 2 2 n f a 構(gòu)造出的d f a 0 圖2 5n f an 的狀態(tài)圖 形式描述n 一( q ， o ，q ，6 ，1 ，僻) 其中q = 仙2 ，封，要構(gòu)造與等價的d f ad ，首先 確定d 的狀態(tài)。有3 個狀態(tài)1 ，2 ，3 ，所以d 有8 個狀態(tài)，d 的每一個狀態(tài)對應(yīng)于 的一個狀態(tài)子集，于是d 的狀態(tài)集為：【囝，講，【2 ， 封，仕2 ，扎3 ， 2 ，3 】i ，仉2 ，3 】 其次確定d 的起始狀態(tài)和接受狀態(tài)。起始狀態(tài)是從1 出發(fā)沿著箭頭能夠到達(dá)的 所有狀態(tài)加上1 本身。有一個箭頭從1 到3 ，故e c l o s e ( 1 y ) 一讓努，d 的接受 狀態(tài)集是的所有包含接受的狀態(tài)子集，即【僻，仉2 ) ，仉3 】- ，他2 ，3 1 1 最后確定d 的轉(zhuǎn)移函數(shù)。d 的每一個狀態(tài)遇到輸入o 到一個地方、遇到輸入1 到一個地方。 狀態(tài)2 遇到輸入o 到2 和3 ，但是從2 和3 不能沿著箭頭走得更遠(yuǎn)，所以在d 中， 狀態(tài)| 【2 遇到輸a o 到 2 ，3 】。因為在中，狀態(tài)2 遇到1 只能到狀態(tài)3 ，并且不能 從3 沿著s 箭頭走的更遠(yuǎn)，所以在d 中，狀態(tài)【2 】遇到輸入1 走到狀態(tài)【3 。因為 在中沒有0 箭頭從狀態(tài)1 射出，所以在d 中狀態(tài)m 遇到0 走到g 。狀態(tài) 1 遇 到l 走到 2 。因為在中狀態(tài)3 遇到0 走到1 、而1 又沿著g 箭頭回到3 ，所以在d 中狀態(tài) 3 】遇到0 走到n 封，狀態(tài) 遇到1 走到g 。 因為1 沒有0 箭頭指向任何狀態(tài)，2 用0 箭頭指向2 和3 ，并且2 和3 都沒有 用s 箭頭指向任何地方，所以狀態(tài)仉2 遇到0 走到 2 ，3 。狀態(tài)詛2 遇到1 走到 2 ，毋。繼續(xù)按照這個方式進(jìn)行，可以得到d 的狀態(tài)圖。 圖2 6 例2 2 3n f an 等價的d f ad 的狀態(tài)圖 由定理2 2 1 可以直接得到下面兩個推論 推論2 2 4 一個語言被某個d f a 所接受，當(dāng)且僅當(dāng)被某個n f a 所接受。 推論2 2 5 一個語言l 被某個占一n f a 接受，當(dāng)且僅當(dāng)被某個d f a 所接受。 1 6 第三章確定型有窮自動機(jī)的極小化 3 1 確定型有窮自動機(jī)的極小化 確定型有窮自動機(jī)( d f a ) 的極小化仍是有窮自動機(jī)應(yīng)用及實現(xiàn)的重要問 題之一。d f a 的極小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系，便于其存儲實現(xiàn)。便于 建立用d f a 描述的任務(wù)模型，一些理論問題也與極小化思想有關(guān)( 6 朱征宇，朱 慶生，2 0 0 1 ； 7 朱征字，朱慶生2 0 0 3 1 5 劉大本，2 0 0 5 ) 。 前面我們已經(jīng)提到過，狀態(tài)的極小化過程是指利用等價性將自動機(jī)的狀態(tài)集 劃分為一些不相交的子集，使得任何兩個不同的子集中的狀態(tài)都是可區(qū)分的，而 同一個子集中的任何兩個狀態(tài)都是等價的。最后，我們可以將形成的等價類用其 中一個元素代表。這就實現(xiàn)了自動機(jī)的極小化而不改變它們識別的語言。 下面我們來看一個例子 例3 。1 有窮自動機(jī)ml i t ( q ，6 ，q o ，f ) ，其中q = 恤，b ，c ，d ，e ，f ，g ，何 ， 芝一 o ，母，f 。怛 。圖3 1 所示 圖3 1有窮自動機(jī)m 根據(jù)第二章確定型有窮自動機(jī)狀態(tài)等價定義，可以做出如下判斷： 首先考慮狀態(tài)哇和g 。串f 不可區(qū)分這兩者，因為它們都是非接受狀態(tài)；串0 不 可區(qū)分這兩者，因為在輸h o 時a ( a ，0 ) f l i t b ，a ( g ，0 ) 一g ，二者分別到達(dá)狀態(tài)b 和 g ，這些狀態(tài)也是非接受的，同樣，串1 不可區(qū)分a 和g ，因為此時兩者分別到 達(dá)f 和e ，都是非接受的。串0 1 區(qū)分a 和g ，因為6 似，0 1 ) - c ，6 + ( g ，0 1 ) ；e ， 1 7 c 是接受狀態(tài)，e 是非接受狀態(tài)。 同樣的，我們考慮狀態(tài)a 和e ，在輸入占上，a 和e 都不是接受的，所以s 不區(qū)分這兩者；在輸入1 上，二者都到達(dá)狀態(tài)f ，因此以1 開頭的串都不區(qū)分a 和 ，即慨，6 似，i x ) l i l t6 。但，l x ) 。我們再考慮以。開頭的字符串的情況，串 o 使二者分別到達(dá)b 和日，b 和日都不是接受的，所以串0 本身不區(qū)分4 和e ， 但是b 和日在輸入1 上都到達(dá)c ，在輸入0 都到達(dá)g ，因此以0 開頭的所有輸入 都不能區(qū)分a 和e ，綜上所述，無論輸入什么樣的串都不能區(qū)分a 和e ，表示a 和e 是等價狀態(tài)。樹圖分割法搜索例3 1 中所有不可區(qū)分的狀態(tài)，如下圖： 輸入字符 儼，c ，g ， 輸入字 應(yīng)得到 岡 1 _ j 圖3 2 樹圖分割法搜索m 中所有不可區(qū)分的狀態(tài)對 搜索的基本原則是：在同樣的輸入條件下其相應(yīng)的次態(tài)應(yīng)彼此等價。這可能存在 三種情況：( 1 ) 對應(yīng)次態(tài)相同；( 2 ) 其次態(tài)就是兩個現(xiàn)態(tài)本身；( 3 ) 其次態(tài)是彼 此等價的。首先將所有狀態(tài)分割成可接受狀態(tài)集合f 一 c 】- 和不可接受狀態(tài)集合。 q 1 = 0 4 ，b ，d ，e ，f ，g ，好) ，6 ( 彳，0 ) - b ，6 ( 曰，0 ) 一g ，6 ( d ，0 ) = c ，6 ( ，0 ) 。h ， 6 ( f ，0 ) = c ，6 ( g ，0 ) 一g ，6 ( 日，0 ) 。g ，所以在q 1 中輸入字符0 得到對應(yīng)的轉(zhuǎn)換后 的狀態(tài)集為q 1 0 - - b ，g ，c ，h ，c ，g ，g ) ，在例3 1 中6 即，1 ) 一f ，6 p ，1 ) tc j 6 ( d ，1 ) 一g ，6 陋，1 ) 一f ，6 ( f ，1 ) eg ，6 ( g ，1 ) te ，6 ( 日，1 ) 二c 因此在q l 中輸入1 得到對應(yīng)的轉(zhuǎn)換后的狀態(tài)集合為q 1 ，。儼，c ，g ，f ，g ，e ，c ，根據(jù)不可區(qū)分定義可 以得到如下結(jié)論：壇，6 p ，l x ) n f 彩營6 餌，l x ) f l f - a ， 6 ( 曰，0 x ) a f 乒彩靜6 餌，0 x ) c if a ，6 + ( d ，h ) nf - 彩營6 ( f ，a x ) n f 一彩， 6 ( d ，帆) n ，一彩營6 + 仃，0 x ) nf 一在第一步中就可以判斷口和日，d 和f 是 不可區(qū)分的，第二步再在剩余的無法判斷的狀態(tài)集中輸入長度為2 的字符，進(jìn)行 判斷，直到求出所有的不可區(qū)分的狀態(tài)對，將所有不可區(qū)分的狀態(tài)進(jìn)行合并。就 得到例3 1 的極小 如圖： 圖3 3m 的極小化自動機(jī) 樹圖分割法3 2 ( 1 ) 首先將d f a 所有的狀態(tài)分割成可接受狀態(tài)和不可接受狀態(tài)集。 ( 2 ) 用雙圓圈來標(biāo)記最大的不可區(qū)分的狀態(tài)集合。 。 ( 3 ) 將d f a 所有輸入字符按某一個順序排列。 ( 4 ) 依次輸入字符進(jìn)行判斷，直到求出最大不可區(qū)分狀態(tài)集為止。 下面我們再來看一個例子進(jìn)一步說明樹圖分割法。 例3 3 設(shè)m 一( q ，6 ，日。，f ) 是一臺確定型有窮自動機(jī)，q 一 o ，1 , 2 ，3 ，4 ， q 。= 0 ，f 一 4 】，一和，6 ，m 的狀態(tài)轉(zhuǎn)換圖如下： 1 9 n 圖3 4m 的狀態(tài)圖 用樹圖分割法來分析例3 3 ： 不 0 ，1 ，2 ，3 ，4 j 丁接受狀態(tài)可接受狀 圖3 5樹圖分割法搜索m 不可區(qū)分的狀態(tài) 首先將m 的狀態(tài)分割成可接受和不可接受的狀態(tài)集合，因為可接受的狀態(tài)和不 可接受狀態(tài)是可以區(qū)分的，再分別對可接受狀態(tài)集合和不可接受狀態(tài)集合輸入字 符進(jìn)行判斷找出不可區(qū)分的狀態(tài)，在例3 3 中，可接受的狀態(tài)只有一個是狀態(tài)4 ， 所以狀態(tài)4 與其它的狀態(tài)都是可區(qū)分的。在不可接受集合中，先輸入長度為1 的 字符a , b 來搜索在一步內(nèi)不可區(qū)分的狀態(tài)，狀態(tài)3 與其它狀態(tài)都是可以區(qū)分的， 而且可以判斷狀態(tài)0 和2 是在任何情況下都是不可區(qū)分的，最后求出所有不可區(qū) 分的狀態(tài)，將所有不可區(qū)分的對合并成一個狀態(tài)，就得到原自動機(jī)的極小化自動 機(jī)。由圖3 5 判斷出的不可區(qū)分的狀態(tài)對進(jìn)行合并，得到例3 3 中自動機(jī)m 的 極小化自動機(jī)。如下圖： 2 0 圖3 6 例3 3 的極小化自動機(jī) 這階段的主要任務(wù)是采用樹圖分割法來極小化d f a 。該方法的主要思想是：將 d f a 分割成一些不相交的子集，使得任何不同兩個子集的狀態(tài)是可區(qū)分的，而 同一子集中任何兩個狀態(tài)是不可區(qū)分的。也就是說，構(gòu)造狀態(tài)集的一個劃分，再 將這個劃分中的每個子集作為新的狀態(tài)，就得到等價的極小化的d f a 。下面證