NFA到DFA的转换

问题陈述

设X = (Q_x, ∑, δ_x, q₀, F_x)为一个接受语言L(X)的NFA。我们必须设计一个等价的DFAY = (Q_y, ∑, δ_y, q₀, F_y)，使得L(Y) = L(X)。以下过程将NFA转换为其等价的DFA -

算法

输入 - 一个NFA

输出 - 一个等价的DFA

步骤1 - 从给定的NFA创建状态表。

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

步骤3 - 将DFA的起始状态标记为q0（与NFA相同）。

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

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

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

示例

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

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

DFA的状态图如下所示 -