DFA 最小化

使用 Myphill-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 − 我们将尝试用绿色复选标记传递性地标记状态对。如果我们向状态"a"和"f"输入 1，它将分别转到状态"c"和"f"。(c, f) 已经标记，因此我们将标记对 (a, f)。现在，我们向状态"b"和"f"输入 1；它将分别转到状态"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 中的每个分区，如果 P_k 中的状态是 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 如下 −