【編譯原理】DFA最小化算法

DFA的定義

DFA是Determinant Finite Automata，確定性有窮自動機這個定義有幾個關鍵點

• 確定性，Determinant的，也就是說，對于一個串，只有一種可接受方法。(這等價于不存在符號相同的邊。)

• 有限，Finite，也就是說節點數量是有限的。

數學地來說:DFA是一個五元組，包括\((S,state,\Sigma,Mov,T)\)：初始狀態，狀態，字符集，狀態轉移函數，結束狀態。

對于OIer的快速入門：一個AC自動機/SAM就是一個DFA，一個\(state\)可以對應成圖上的一個節點，\(\Sigma\)就是AC自動機/SAM的字符集，\(S\)就是AC自動機/SAM的開始節點，\(T\)就是接受節點，而\(Mov(A,b)=C\)就是查詢\(A\)走一條字符為\(b\)的邊到了哪個節點(\(C\))，如果沒有這條邊那么\((A,b)\)沒有不在\(Mov\)函數的定義域。

本文不對DFA做過于嚴格的定義。

最小DFA定義

可接受字符串集合相同的DFA稱為等價DFA，最小DFA的定義是所有等價DFA中節點最小的，可以證明節點最小的DFA只有一種。

狀態(也就是DFA的某個節點)的可區分性

兩個點不可區分記為\(A\sim B\)

\(A\sim B\)，A和B不可區分當且僅當兩個狀態的所有出邊都對應不可區分。

所有出邊對應不可區分當且僅當\(\not \exists c\in \Sigma , Mov(A,c)\not \sim Mov(B,c)\)，即符號對應的出邊到達的節點不可區分

迭代法求最小化DFA

初始情況，我們能確定，至少所有結束狀態和其他節點(非結束狀態)是不一樣的。

算法的思路是不斷尋找可區分的點，并且分裂，層次有點類似B算法求最小生成樹。

• 初始情況：\(\prod_0 = S_1,S_2\)，\(S_1\)是所有結束狀態，\(S_2\)是所有非結束狀態

• 迭代方法：假設本次為第\(n\)次迭代。

  • 枚舉一個\(S_k\in \prod_{n-1}\)

  • 枚舉所有\(c\in \Sigma\)，得到一個集合\(Mov(S_k,c)=\{Mov(X,c):X\in S_k\}\)

    • 確認是否每個\(Mov(X,c)\)都有定義(有這條邊)，都有定義則通過
    • 確認是否存在\(S_t\in \prod_{n-1}\)，\(Mov(S_k,c)\subseteq S_t\)(所有邊都不可區分)，存在\(S_t\)則通過

  • 若通過以上兩種檢查(說明\(S_k\)不可區分)，則\(S_k\rightarrow \prod_n\)(加入這個集合)

  • 若沒有通過以上兩種檢查，則將\(S_k\)不相交地劃分成若干個極大集合\(T_1,T_2\dots T_m\)使得\(\forall i,\exist S_t\in \prod_{n-1},Mov(T_i,c)\subseteq S_t\)，這里極大集合的意思是, \(\not \exist i\not = j, \textbf{ s.t. } Mov(T_i,c)\cup Mov(T_j,c) \subseteq S_t\)

    隨后執行\(T_1,T_2\dots T_m \rightarrow \prod\)

  (人話:將\(S_k\)分裂成若干集合，使得集合內的點的所有出邊在\(\prod_{n-1}\)意義下中不可區分，并且希望分裂出的集合數量最小)

復雜度分析

這個論文

(記得把后綴改成.pdf)

簡單實現迭代可以做到\(O(m \log m)\)

指的一提的是，這個算法的發明者最終獲得了圖靈獎！

代碼

代碼到時候再說吧。