Automata Theory 简明教程

设 X = (Qx, ∑, δx, q0, Fx) 是接受语言 L(X) 的 NDFA。我们必须设计一个等效 DFA Y = (Qy, ∑, δy, q0, Fy) ，使得 L(Y) = L(X) 。以下过程将 NDFA 转换为其等效 DFA −

Input − NDFA

Output − 等效 DFA

Step 1 − 根据给定的 NDFA 创建状态表。

Step 2 − 根据等效 DFA 的可能的输入字母创建一个空白状态表。

Step 3 − 标记为 q0 的 DFA 的起始状态（与 NDFA 相同）。

Step 4 − 找出对于每个可能的输入字母的状态 {Q0, Q1,…​ , Qn} 的组合。

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

Step 6 − 包含 NDFA 的任何最终状态的状态是等效 DFA 的最终状态。

我们考虑下图所示的 NDFA。

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

DFA 的状态图如下所示 −