NDFA 到 DFA 转换

---

问题陈述

令X = (Q _x , Σ, δ _x , q ₀ , F _x )为接受语言 L(X) 的 NDFA。我们必须设计一个等效的 DFA Y = (Q _y , Σ, δ _y , q ₀ , F _y )使得L(Y) = L(X)。以下过程将 NDFA 转换为其等效的 DFA -

算法

输入- NDFA

输出- 等效的 DFA

步骤 1 - 根据给定的 NDFA 创建状态表。

步骤 2 - 在等效 DFA 的可能输入字母下创建一个空白状态表。

步骤 3 - 用 q0 标记 DFA 的开始状态（与 NDFA 相同）。

步骤 4 - 找出每个可能的输入字母表的状态 {Q ₀ , Q ₁ ,... , Q _{n } 的组合。}

步骤 5 - 每次我们在输入字母列下生成新的 DFA 状态时，我们都必须再次应用步骤 4，否则转到步骤 6。

步骤 6 - 包含 NDFA 任何最终状态的状态是等效 DFA 的最终状态。

例子

让我们考虑下图所示的 NDFA。

使用上述算法，我们找到其等价的DFA。DFA的状态表如下所示。

DFA 的状态图如下 -