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^等价的。取一个计数器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^个等效集并使它们成为简化 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 中有 3 个状态。减少的 DFA 如下 -