消除ε转换的自动机

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

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

例：

将以下带ε的NFA转换为不带ε的NFA。

解决方案：我们首先将获得q0，q1和q2的ε闭包，如下所示：

ε-closure(q0) = {q0}
ε-closure(q1) = {q1, q2}
ε-closure(q2) = {q2}

现在，每个输入符号上的δ’转换为：

δ'(q0, a) = ε-closure(δ(δ^(q0, ε), a))
              = ε-closure(δ(ε-closure(q0), a))
              = ε-closure(δ(q0, a))
              = ε-closure(q1)
              = {q1, q2}

δ'(q0, b) = ε-closure(δ(δ^(q0, ε), b))
              = ε-closure(δ(ε-closure(q0), b))
              = ε-closure(δ(q0, b))
              = Ф

现在，q1上的δ’转换为：

δ'(q1, a) = ε-closure(δ(δ^(q1, ε), a))
              = ε-closure(δ(ε-closure(q1), a))
              = ε-closure(δ(q1, q2), a)
              = ε-closure(δ(q1, a) ∪ δ(q2, a))
              = ε-closure(Ф ∪ Ф)
              = Ф

δ'(q1, b) = ε-closure(δ(δ^(q1, ε), b))
              = ε-closure(δ(ε-closure(q1), b))
              = ε-closure(δ(q1, q2), b)
              = ε-closure(δ(q1, b) ∪ δ(q2, b))
              = ε-closure(Ф ∪ q2)
              = {q2}

q2上的δ’转换为：

δ'(q2, a) = ε-closure(δ(δ^(q2, ε), a))
              = ε-closure(δ(ε-closure(q2), a))
              = ε-closure(δ(q2, a))
              = ε-closure(Ф)
              = Ф

δ'(q2, b) = ε-closure(δ(δ^(q2, ε), b))
              = ε-closure(δ(ε-closure(q2), b))
              = ε-closure(δ(q2, b))
              = ε-closure(q2)
              = {q2}

现在，我们将总结所有计算出的δ’跃迁：

δ'(q0, a) = {q0, q1}
δ'(q0, b) = Ф
δ'(q1, a) = Ф
δ'(q1, b) = {q2}
δ'(q2, a) = Ф
δ'(q2, b) = {q2}

过渡表可以是：

状态q1和q2变为最终状态，因为q1和q2的ε闭包包含最终状态q2。 NFA可以通过以下过渡图显示：