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的状态图如下 −