从 NFA 转换为 DFA

在本节中，我们将讨论将 NFA 转换为其等效 DFA 的方法。 在 NFA 中，当为当前状态提供特定输入时，机器会转到多个状态。 它可能在给定的输入符号上具有零个、一个或多个移动。 另一方面，在 DFA 中，当为当前状态提供特定输入时，机器仅转到一个状态。 DFA 在给定的输入符号上只有一个移动。

令 M = (Q, ∑, δ, q0, F) 是一个接受语言 L(M) 的 NFA。 应该存在等效的 DFA，表示为 M' = (Q', ∑', q0', δ', F')，使得 L(M) = L(M')。

将 NFA 转换为 DFA 的步骤

步骤 1： 最初 Q' = ϕ

步骤 2： 将 NFA 的 q0 添加到 Q'。 然后从这个起始状态找到转移。

步骤 3： 在 Q' 中，为每个输入符号找到可能的状态集。 如果此状态集不在 Q' 中，则将其添加到 Q'。

步骤 4： 在 DFA 中，最终状态将是包含 F（NFA 的最终状态）的所有状态

示例 1

将给定的 NFA 转换为 DFA。

解决方案： 对于给定的转换图，我们将首先构建转换表。

现在我们将为状态 q0 获得 δ' 转换。

状态 q1 的 δ' 转换获得如下

状态 q2 的 δ' 转换获得如下

现在我们将获得 [q1, q2] 的 δ' 转换。

状态 [q1, q2] 也是最终状态，因为它包含最终状态 q2。 构建的 DFA 的转换表将是

转换图将是

可以消除状态 q2，因为 q2 是一个不可达状态。

示例 2

将给定的 NFA 转换为 DFA。

解决方案： 对于给定的转换图，我们将首先构建转换表。

现在我们将为状态 q0 获得 δ' 转换。

状态 q1 的 δ' 转换获得如下

现在我们将获得 [q0, q1] 的 δ' 转换。

类似地，

由于在给定的 NFA 中，q1 是最终状态，因此在 DFA 中，无论 q1 存在于何处，该状态都将成为最终状态。 因此，在 DFA 中，最终状态为 [q1] 和 [q0, q1]。 因此，最终状态集 F = {[q1], [q0, q1]}。

构建的 DFA 的转换表将是

转换图将是

甚至我们可以更改 DFA 的状态名称。

假设

使用这些新名称，DFA 将如下所示