可以将带有ε的NFA转换为没有ε的NFA，并且可以将没有ε的NFA转换为DFA。为此，我们将使用一种方法，该方法可以删除给定NFA中的所有ε过渡。该方法将是：
- 找出Q中每个状态的所有ε跃迁。这将称为ε-closure{q1}，其中qi∈Q。
- 然后可以获得δ’ 跃迁。 δ’ 跃迁意味着δ运动的ε闭合。
- 对每个输入符号和给定NFA的每个状态重复步骤2。
- 使用结果状态，可以建立没有ε的等效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}过渡表可以是：
| 状态 | 一种 | b |
|---|---|---|
| →q0 | {q1, q2} | ?F |
| *q1 | ?F | {q2} |
| *q2 | ?F | {q2} |
文章图片
