消除 ε 转换

带有 ε 的 NFA 可以转换为没有 ε 的 NFA，并且这个没有 ε 的 NFA 可以转换为 DFA。 为此，我们将使用一种方法，该方法可以从给定的 NFA 中删除所有 ε 转换。 该方法是

1. 找出从 Q 的每个状态的所有 ε 转换。这将被称为 ε-closure{q1}，其中 qi ∈ Q。
2. 然后可以获得 δ' 转换。 δ' 转换意味着 δ 移动上的 ε-closure。
3. 对每个输入符号和给定 NFA 的每个状态重复步骤 2。
4. 使用结果状态，可以构建没有 ε 的等效 NFA 的转换表。

示例

将以下带有 ε 的 NFA 转换为没有 ε 的 NFA。

解决方案： 我们将首先获得 q0、q1 和 q2 的 ε-closures 如下

现在获得了每个输入符号的 δ' 转换，如下所示

现在获得了 q1 上的 δ' 转换，如下所示

获得了 q2 上的 δ' 转换，如下所示

现在，我们将总结所有计算出的 δ' 转换

转换表可以是

状态 q1 和 q2 变为最终状态，因为 q1 和 q2 的 ε-closure 包含最终状态 q2。 NFA 可以通过以下转换图显示