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 如下所示 -