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

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

基本介紹

• 中文名：確定有限狀態自動機最小化
• 領域：計算機

最小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最小化算法。