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

等價的最小DFA，等價狀態都被合併成了一個。

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

最小DFA

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

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

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

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

不可達狀態

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

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中移去並不會影響其接受的語言。

等價狀態

Hopcroft算法

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

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

P := {F, Q \ F};
W := {F};
while (W is not empty) do
     choose and remove a set A from W
     for each c in Σ do
          let X be the set of states for which a transition on c leads to a state in A
          for each set Y in P for which X ∩ Y is nonempty and Y \ X is nonempty do
               replace Y in P by the two sets X ∩ Y and Y \ X
               if Y is in W
                    replace Y in W by the same two sets
               else
                    if |X ∩ Y| <= |Y \ X|
                         add X ∩ Y to W
                    else
                         add Y \ X to W
          end;
     end;
end;

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

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

當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)$ ，結果取決於建模平均情況行為的自動機隨機選取分佈方式。^[6]

Brzozowski算法

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

NFA最小化

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

參見

註釋

^ Hopcroft, Motwani & Ullman (2001), Section 4.4.3, "Minimization of DFA's".
^ Hopcroft & Ullman (1979), Section 3.4, Theorem 3.10, p.67
^ Hopcroft, Motwani & Ullman (2001), Section 4.4.3, "Minimization of DFA's", p. 159, and p. 164 (remark after Theorem 4.26)
^ Hopcroft (1971); Aho, Hopcroft & Ullman (1974)
^ Berstel et al. (2010).
^ David (2012).
^ For instance, the language of binary strings whose nth symbol is a one requires only $n + 1$ states, but its reversal requires $2 n$ states. Leiss (1981) provides a ternary n-state DFA whose reversal requires $2 n$ states, the maximum possible. For additional examples and the observation of the connection between these examples and the worst-case analysis of Brzozowski's algorithm, see Câmpeanu et al. (2001).
^ Hopcroft, Motwani & Ullman (2001), Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.
^ Kameda & Weiner (1970).

參考文獻

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最小化

[1] Hopcroft, Motwani & Ullman (2001), Section 4.4.3, "Minimization of DFA's".

[2] Hopcroft & Ullman (1979), Section 3.4, Theorem 3.10, p.67

[3] Hopcroft, Motwani & Ullman (2001), Section 4.4.3, "Minimization of DFA's", p. 159, and p. 164 (remark after Theorem 4.26)

[4] Hopcroft (1971); Aho, Hopcroft & Ullman (1974)

[bbcf-5] Berstel et al. (2010).

[FOOTNOTEDavid2012-6] David (2012).

[7] For instance, the language of binary strings whose nth symbol is a one requires only $n + 1$ states, but its reversal requires $2 n$ states. Leiss (1981) provides a ternary n-state DFA whose reversal requires $2 n$ states, the maximum possible. For additional examples and the observation of the connection between these examples and the worst-case analysis of Brzozowski's algorithm, see Câmpeanu et al. (2001).

[8] Hopcroft, Motwani & Ullman (2001), Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.

[FOOTNOTEKamedaWeiner1970-9] Kameda & Weiner (1970).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]