从NFA到DFA的转换

NFA可以在给定输入符号上从给定状态进行零次、一次或多次移动。NFA也可以有空移动（没有输入符号的移动）。另一方面，DFA从给定状态到给定输入符号只有一次移动。

从NFA到DFA的转换 假设有一个NFA N 识别一种语言L。然后DFA D 可以为语言L构造为： 第一步：最初Q’=ɸ。 第2步：将q0添加到Q’中。 步骤3：对于Q’中的每个状态，使用NFA的转换函数找到每个输入符号的可能状态集。如果这组状态不在Q’中，则将其添加到Q’中。 步骤4：DFA的最终状态将是包含F的所有状态（NFA的最终状态）

实例 考虑下面的NFA，如图1所示。 以下是NFA的各种参数。 Q={q0，q1，q2} ∑ = （a，b） F={q2} δ（NFA的过渡函数）

第一步：Q’=ɸ 第2步：Q’={q0} 步骤3：对于Q’中的每个状态，找到每个输入符号的状态。 目前，Q’中的状态为q0，使用NFA的转换函数在输入符号a和b上查找q0的移动，并更新DFA的转换表。

δ’（DFA的过渡函数） 现在{q0，q1}将被视为一个单一的状态。因为它的条目不在Q’中，所以将其添加到Q’中。 所以Q’={q0，{q0，q1}

现在，在DFA的转换表中，不同输入符号上从状态{q0，q1}的移动不存在，我们将按如下方式计算： δ’（{q0，q1}，a）=δ（q0，a）∪ δ（q1，a）={q0，q1} δ’（{q0，q1}，b）=δ（q0，b）∪ δ（q1，b）={q0，q2} 现在我们将更新DFA的转换表。

δ’（DFA的过渡函数） 现在{q0，q2}将被视为一个单一的状态。因为它的条目不在Q’中，所以将其添加到Q’中。 所以Q’={q0，{q0，q1}，{q0，q2}

现在，在DFA的转换表中，不同输入符号上从状态{q0，q2}开始的移动不存在，我们将按如下方式计算： δ’（{q0，q2}，a）=δ（q0，a）∪ δ（q2，a）={q0，q1} δ’（{q0，q2}，b）=δ（q0，b）∪ δ（q2，b）={q0} 现在我们将更新DFA的转换表。

δ’（DFA的过渡函数） 由于没有生成新的状态，我们完成了转换。DFA的最终状态将是以q2作为其组件的状态，即{q0，q2}

以下是DFA的各种参数。 Q’={q0，{q0，q1}，{q0，q2} ∑ = （a，b） F={q0，q2}}和过渡函数δ’，如上所示。上述NFA的最终DFA如图2所示。 注： 有时，将正则表达式转换为DFA并不容易。首先可以将正则表达式转换为NFA，然后将NFA转换为DFA。

问题: 与正则表达式（0+1）*（10）相对应的最小确定性有限自动机中的状态数为。 解决方案： 首先，我们将对上述表达式进行NFA。要为（0+1）*生成NFA，NFA将在输入符号0或1上处于相同的状态q0。然后对于串联，我们将添加两个移动（q0到q1表示1，q1到q2表示0），如图3所示。 本文由Sonal Tuteja撰稿。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论