確定有限狀態自動機最小化

自動機理論計算機科學的一個分支)中,確定有限狀態自動機最小化是將給定的確定有限狀態自動機(DFA, Deterministic Finite Automaton)改造為等價且擁有最少狀態的DFA的過程。這裡,兩個DFA等價意味著他們識別相同的正則語言。

基本介紹

  • 中文名:確定有限狀態自動機最小化
  • 領域:計算機
最小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最小化算法。

相關詞條

熱門詞條

聯絡我們