DFA 最小化

---

---

使用 Myhill-Nerode 定理進行 DFA 最小化

演算法

輸入 - DFA

輸出 - 最小化的 DFA

步驟 1 - 為所有狀態對 (Q_i, Q_j) 繪製表格，這些狀態對不一定直接連線 [最初所有狀態均未標記]

步驟 2 - 考慮 DFA 中的每個狀態對 (Q_i, Q_j)，其中 Q_i ∈ F 且 Q_j ∉ F 或反之，並標記它們。[此處 F 是最終狀態集]

步驟 3 - 重複此步驟，直到我們無法再標記任何狀態 -

如果存在未標記的狀態對 (Q_i, Q_j)，則如果對於某個輸入字母表，狀態對 {δ (Q_i, A), δ (Q_i, A)} 被標記，則標記它。

步驟 4 - 將所有未標記的狀態對 (Q_i, Q_j) 組合起來，並使它們成為簡化後的 DFA 中的單個狀態。

示例

讓我們使用演算法 2 來最小化下面顯示的 DFA。

步驟 1 - 我們為所有狀態對繪製表格。

步驟 2 - 我們標記狀態對。

步驟 3 - 我們將嘗試傳遞地標記狀態對，用綠色複選標記。如果我們將 1 輸入到狀態“a”和“f”，它將分別轉到狀態“c”和“f”。(c, f) 已被標記，因此我們將標記對 (a, f)。現在，我們將 1 輸入到狀態“b”和“f”；它將分別轉到狀態“d”和“f”。(d, f) 已被標記，因此我們將標記對 (b, f)。

步驟 3 之後，我們得到了未標記的狀態組合 {a, b} {c, d} {c, e} {d, e}。

我們可以將 {c, d} {c, e} {d, e} 重新組合為 {c, d, e}

因此我們得到了兩個組合狀態 - {a, b} 和 {c, d, e}

因此，最終最小化的 DFA 將包含三個狀態 {f}、{a, b} 和 {c, d, e}

使用等價定理進行 DFA 最小化

如果 X 和 Y 是 DFA 中的兩個狀態，如果它們不可區分，我們可以將這兩個狀態組合成 {X, Y}。如果至少存在一個字串 S，使得 δ (X, S) 和 δ (Y, S) 中的一個是接受狀態而另一個不是接受狀態，則這兩個狀態是可區分的。因此，當且僅當所有狀態都可區分時，DFA 才是最小的。

演算法 3

步驟 1 - 所有狀態 Q 分為兩個分割槽 - 最終狀態和非最終狀態，並表示為 P₀。分割槽中的所有狀態都是 0^th 等價的。取一個計數器 k 並將其初始化為 0。

步驟 2 - 將 k 加 1。對於 P_k 中的每個分割槽，如果它們是 k 可區分的，則將 P_k 中的狀態劃分為兩個分割槽。如果存在輸入 S 使得 δ(X, S) 和 δ(Y, S) 是 (k-1) 可區分的，則此分割槽中的兩個狀態 X 和 Y 是 k 可區分的。

步驟 3 - 如果 P_k ≠ P_k-1，則重複步驟 2，否則轉到步驟 4。

步驟 4 - 將 k^th 等價集組合起來，並將它們作為簡化後的 DFA 的新狀態。

示例

讓我們考慮以下 DFA -

讓我們將上述演算法應用於上述 DFA -

• P₀ = {(c,d,e), (a,b,f)}
• P₁ = {(c,d,e), (a,b),(f)}
• P₂ = {(c,d,e), (a,b),(f)}

因此，P₁ = P₂。

簡化後的 DFA 中有三個狀態。簡化後的 DFA 如下所示 -