确定有限状态自动机最小化

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

## 最小 DFA

對於每個正則語言，都存在一個**最小自動機**接受它，即一個有著最小狀態數目的 DFA，且這個 DFA 是唯一的（除去狀態命名不同的差別）。 最小 DFA 保證了其在模式匹配等計算應用中開銷的最小。

在不影響原始 DFA 所接受語言的情況下，有兩類狀態可以被移除或合併，以實現最小化過程。

* **不可達狀態**指 DFA 在任意輸入串下都無法達到的狀態。
* **等價狀態**指在同一輸入串下不產生區別的狀態。

DFA 最小化通常要經歷三個步驟，分別對應於相關狀態的移除或合併。因為等價狀態的消解開銷高昂，通常會將其放到最後一步。

## 不可達狀態

DFA $M=(Q,\Sigma ,\delta ,q_{0},F)$ 的狀態 $p$ 是不可達的，若不存在 $\Sigma ^{*}$ 上的串 $w$ ，使得 $p=\delta ^{*}(q_{0},w)$ 。可達狀態可以用如下算法來找到：

將不可達狀態從 DFA 中移去並不會影響其接受的語言。

## 等價狀態

### Hopcroft 算法

根據 Hopcroft (1971)，以下算法可用來合併等價狀態。該算法基於劃分細化，按照狀態的行為將 DFA 各狀態分組。這些分組即 Myhill-Nerode 等價關係下的等價類，滿足同一等價類中的兩個狀態在相同的輸入下有相同的行為。即對劃分中屬於同一等價類的任意兩個狀態 $p_{1}$ 和 $p_{2}$ ，對所有輸入串 $w$ ， $w$ 所導致的轉移應當始終將 $p_{1}$ 和 $p_{2}$ 帶到相同的狀態，或都接受，或都拒絕。而不應當出現 $w$ 將 $p_{1}$ 帶到了一個接受狀態，而將 $p_{2}$ 帶到了一個拒絕狀態，反之亦然。

下面以偽代碼形式描述了該算法：

算法從一個粗劃分開始：在 Myhill–Nerode 關係下等價的狀態對都屬於劃分中的同一子集，但此時不等價的狀態對也可能被劃入了同一子集。 上述算法逐漸將劃分細化為大量較小的集合，每一步都將各狀態集分為不等價的一對子集。起始劃分是將那些明顯沒有相同行為的狀態分為接受狀態和拒絕狀態。隨後算法在每一輪都會從當前劃分中選中一個集合 $A$ 和一個輸入符 $c$ ，再將劃分中的每個集合分成兩個子集（可能為空）：在輸入 $c$ 下可以被帶到 $A$ 中狀態的狀態，和在輸入 $c$ 下不會被帶到 $A$ 中狀態的狀態。由於 $A$ 已知和劃分中其他集合具有不同的行為， $A$ 的子集也具有該性質。當找不到細分的時候，算法終止。

最壞情況下，算法的運行時間是 $O(ns\log n)$ ，其中 $n$ 為狀態數， $s$ 為字母表大小。這一時間界的得出是由於，對自動機的每 $ns$ 個轉移，每步轉移在切分步驟中參與了 $O(\log n)$ 的複雜度。劃分細分的資料結構可以允許每步切分的操作時間和轉移次數成比例。 這一算法仍是解決該問題的已知最有效算法，對某些輸入的隨機分布，算法平均複雜度的時間界要更好，為 $O(\log \log n)$ .

當 Hopcroft 算法已經將 DFA 中的狀態劃分為等價類，最小 DFA 就可以通過為每個等價類生成一個狀態來構造了。若 $S$ 是劃分 $P$ 的一個狀態集， $s$ 是 $S$ 中的一個狀態， $c$ 是一個字符輸入；那麼最小 DFA 的狀態轉移從 $S$ 起始，在 $c$ 下轉移到原自動機從狀態 $s$ 在輸入 $c$ 下轉移到的狀態集。最小 DFA 的起始狀態是包含有原 DFA 起始狀態的集合，接受狀態是其成員為原 DFA 中接受狀態的集合。

### Moore 算法

Moore DFA 最小化算法由 Edward F. Moore （1956）給出。與 Hopcroft 算法類似地，它維護一個劃分，且這個劃分的初值為接受和拒絕狀態的劃分，並同樣反覆細化直至無法繼續細化。在每一步中，它都會用 _s_ + 1 個劃分的最粗公細化 (coarsest common refinement) 來替代當前的劃分，這 $s+1$ 個劃分中的一個是當前劃分，其他的 $s$ 個則是當前劃分在轉移函數和在所有輸入符號下的原象。當這一操作無法改善當前劃分時，算法即停止。這個算法在最壞情況下的複雜度是 $O(n^{2}s)$ ：算法的每個步驟都需要 $O(ns)$ ，這是基數排序一個變種用以重排狀態的複雜度，狀態重排使得新劃分下同一集合中狀態的編號順序是接連的。又，最多會有 $n$ 輪，因為除最後一輪外，每輪都使得劃分中的集合數目增加。在 Moore 算法下導致最壞情況的 DFA 最小化問題實例和 Hopcroft 算法是相同的。算法的輪數會比 $n$ 小得多，所以平均上（ $s$ 是常數），其性能可達 $O(n\log n)$ 甚至 $O(n\log \log n)$ ，結果取決於建模平均情況行為的自動機隨機選取分布方式。

### Brzozowski 算法

Brzozowski (1963) 注意到，將 DFA 的邊反轉將產生一個原語言反序的非確定有限狀態自動機 (NFA)。再將這個 NFA 用標準的冪集構造法（只構造轉換後 DFA 的可達狀態）轉換為 DFA，就會產生原語言反序的最小 DFA。重複反轉操作，就可以得到原語言的最小 DFA。Brzozowski 算法在最壞情況下的複雜度是指數的，因為存在這樣的正則語言，其反序的最小 DFA 的規模是原語言 DFA 規模的指數大。 但通常來說這個算法比最壞情況表現得要好。

## NFA 最小化

以上的步驟都對 DFA 有效，可是劃分的方法並不適用於非確定有限狀態自動機 (NFA)。雖然窮舉搜索可以最小化 NFA，但並沒有一個多項式時間的算法可以完成該過程，除非 P=PSPACE（計算複雜性理論中的一個未解決問題，一般認為很可能 P≠PSPACE）。然而的確存在比暴力搜索可能更加有效的 NFA 最小化算法。

## 參見

* 確定有限狀態自動機
* 自動機理論

## 注釋

## 參考文獻

* Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D., 4.13 Partitioning, The Design and Analysis of Computer Algorithms, Addison-Wesley: 157–162, 1974 .
* Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle, Minimization of Automata, Automata: from Mathematics to Applications, European Mathematical Society, 2010, arXiv:1010.5318
* Brzozowski, J. A., Canonical regular expressions and minimal state graphs for definite events, Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y.: 529–561, 1963, MR 0175719 .
* Câmpeanu, Cezar; Culik, Karel, II; Salomaa, Kai; Yu, Sheng, State Complexity of Basic Operations on Finite Languages, 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science **2214**, Springer-Verlag: 60–70, 2001, doi:10.1007/3-540-45526-4\_6 .
* David, Julien, Average complexity of Moore’s and Hopcroft’s algorithms, Theoretical Computer Science, 2012, **417**: 50–65, doi:10.1016/j.tcs.2011.10.011 .
* Hopcroft, John, An _n_ log _n_ algorithm for minimizing states in a finite automaton, Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press: 189–196, 1971, MR 0403320 . See also preliminary version, Technical Report STAN-CS-71-190 （頁面存檔備份，存於網際網路檔案館）, Stanford University, Computer Science Department, January 1971.
* Hopcroft, John E.; Ullman, Jeffrey D., Introduction to Automata Theory, Languages, and Computation, Reading/MA: Addison-Wesley, 1979, ISBN 0-201-02988-X
* Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D., Introduction to Automata Theory, Languages, and Computation 2nd, Addison-Wesley, 2001 .
* Kameda, Tsunehiko; Weiner, Peter, On the state minimization of nondeterministic finite automata, IEEE Transactions on Computers, 1970, **100** (7), doi:10.1109/T-C.1970.222994 .
* Knuutila, Timo, Re-describing an algorithm by Hopcroft, Theoretical Computer Science, 2001, **250** (1-2): 333–363, MR 1795249, doi:10.1016/S0304-3975(99)00150-4 .
* Leiss, Ernst, Succinct representation of regular languages by Boolean automata (PDF), Theoretical Computer Science, 1981, **13** (3): 323–330, MR 0603263, doi:10.1016/S0304-3975(81)80005-9 .
* Leiss, Ernst, Succinct representation of regular languages by Boolean automata II (PDF), Theoretical Computer Science, 1985, **38**: 133–136, doi:10.1016/0304-3975(85)90215-4
* Moore, Edward F., Gedanken-experiments on sequential machines, Automata studies, Annals of mathematics studies, no. 34, Princeton, N. J.: Princeton University Press: 129–153, 1956, MR 0078059 .
* Sakarovitch, Jacques, Elements of automata theory, Translated from French by Reuben Thomas, Cambridge University Press, 2009, ISBN 978-0-521-84425-3, Zbl 1188.68177

## 外部連結

* 使用 Myhill-Nerode 定理做 DFA 最小化