基本介紹
- 中文名:確定有限狀態自動機最小化
- 領域:計算機
最小DFA,不可達狀態,等價狀態,Moore算法,Brzozowski算法,NFA最小化,
最小DFA
對於每個正則語言,都存在一個最小自動機接受它,即一個有著最小狀態數目的DFA,且這個DFA是唯一的(除去狀態命名不同的差別)。最小DFA保證了其在模式匹配等計算套用中開銷的最小。
在不影響原始DFA所接受語言的情況下,有兩類狀態可以被移除或合併,以實現最小化過程。
- 不可達狀態指DFA在任意輸入串下都無法達到的狀態。
- 等價狀態指在同一輸入串下不產生區別的狀態。
DFA最小化通常要經歷三個步驟,分別對應於相關狀態的移除或合併。因為等價狀態的消解開銷高昂,通常會將其放到最後一步。
不可達狀態
DFA 的狀態 是不可達的,若不存在 上的串 ,使得 。可達狀態可以用如下算法來找到:
let reachable_states := {q0}; let new_states := {q0}; do { temp := the empty set; for each q in new_states do for each c in Σ do temp := temp ∪ {p such that p = δ(q,c)}; end; end; new_states := temp \ reachable_states; reachable_states := reachable_states ∪ new_states;} while (new_states ≠ the empty set); unreachable_states := Q \ reachable_states;
將不可達狀態從DFA中移去並不會影響其接受的語言。
等價狀態
Moore算法
Moore DFA最小化算法由Edward F. Moore(1956)給出。與 Hopcroft 算法類似地,它維護一個劃分,且這個劃分的初值為接受和拒絕狀態的劃分,並同樣反覆細化直至無法繼續細化。在每一步中,它都會用s+ 1個劃分的最粗公細化(coarsest common refinement) 來替代當前的劃分,這 個劃分中的一個是當前劃分,其他的 個則是當前劃分在轉移函式和在所有輸入符號下的原象。當這一操作無法改善當前劃分時,算法即停止。這個算法在最壞情況下的複雜度是 :算法的每個步驟都需要 ,這是基數排序一個變種用以重排狀態的複雜度,狀態重排使得新劃分下同一集合中狀態的編號順序是接連的。又,最多會有 輪,因為除最後一輪外,每輪都使得劃分中的集合數目增加。在Moore算法下導致最壞情況的DFA最小化問題實例和Hopcroft算法是相同的。算法的輪數會比 小得多,所以平均上( 是常數),其性能可達 甚至 ,結果取決於建模平均情況行為的自動機隨機選取分布方式。
Brzozowski算法
Brzozowski (1963) 注意到,將DFA的邊反轉將產生一個原語言反序的非確定有限狀態自動機(NFA)。再將這個NFA用標準的冪集構造法(只構造轉換後DFA的可達狀態)轉換為DFA,就會產生原語言反序的最小DFA。重複反轉操作,就可以得到原語言的最小DFA。Brzozowski算法在最壞情況下的複雜度是指數的,因為存在這樣的正則語言,其反序的最小DFA的規模是原語言DFA規模的指數大。但通常來說這個算法比最壞情況表現得要好。
NFA最小化
以上的步驟都對DFA有效,可是劃分的方法並不適用於非確定有限狀態自動機(NFA)。雖然窮舉搜尋可以最小化NFA,但並沒有一個多項式時間的算法可以完成該過程,除非P=PSPACE(計算複雜性理論中的一個未解決問題,一般認為很可能P≠PSPACE)。然而的確存在比暴力搜尋可能更加有效的NFA最小化算法。