本文概述
- 将带有ε的NFA转换为DFA的步骤
哪里
Q: finite set of states
∑: finite set of the input symbol
q0: initial state
F: final state
δ: Transition function具有∈移动的NFA：如果任何FA包含ε事务或移动，则有限自动机称为带有∈移动的NFA。
ε闭包：给定状态A的ε闭包是指可以从状态A到达的一组状态，只有ε（null）移动，包括状态A本身。
将带有ε的NFA转换为DFA的步骤步骤1：我们将NFA起始状态的ε闭环作为DFA的起始状态。
步骤2：找到可以从现在开始遍历的每个输入符号的状态。也就是说，对于DFA当前状态中存在的每个NFA状态，过渡值的合并及其闭包。
步骤3：如果找到新状态，则将其作为当前状态并重复步骤2。
步骤4：重复步骤2和步骤3，直到DFA转换表中没有新状态为止。
步骤5：将DFA的状态标记为包含NFA的最终状态的最终状态。
范例1：
用ε将NFA转换为其等效的DFA。
文章图片
解：
让我们获得每个状态的ε闭包。
ε-closure {q0} = {q0, q1, q2}
ε-closure {q1} = {q1}
ε-closure {q2} = {q2}
ε-closure {q3} = {q3}
ε-closure {q4} = {q4}现在，让ε闭包{q0} = {q0，q1，q2}为状态A。
因此
δ'(A, 0) = ε-closure {δ((q0, q1, q2), 0) }
= ε-closure {δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0) }
= ε-closure {q3}
= {q3}call it as state B.δ'(A, 1) = ε-closure {δ((q0, q1, q2), 1) }
= ε-closure {δ((q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1) }
= ε-closure {q3}
= {q3} = B.部分DFA为
文章图片
现在，
δ'(B, 0) = ε-closure {δ(q3, 0) }
= ?
δ'(B, 1) = ε-closure {δ(q3, 1) }
= ε-closure {q4}
= {q4}i.e. state C对于状态C：
δ'(C, 0) = ε-closure {δ(q4, 0) }
= ?
δ'(C, 1) = ε-closure {δ(q4, 1) }
= ?DFA将是
文章图片
范例2：
将给定的NFA转换为其等效的DFA。
文章图片
解决方案：让我们获得每个状态的ε闭包。
ε-closure(q0) = {q0, q1, q2}
ε-closure(q1) = {q1, q2}
ε-closure(q2) = {q2}现在我们将获得δ’ 跃迁。令ε-closure（q0）= {q0，q1，q2}称为状态A。
δ'(A, 0) = ε-closure{δ((q0, q1, q2), 0)}
= ε-closure{δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0)}
= ε-closure{q0}
= {q0, q1, q2}δ'(A, 1) = ε-closure{δ((q0, q1, q2), 1)}
= ε-closure{δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1)}
= ε-closure{q1}
= {q1, q2}call it as state Bδ'(A, 2) = ε-closure{δ((q0, q1, q2), 2)}
= ε-closure{δ(q0, 2) ∪ δ(q1, 2) ∪ δ(q2, 2)}
= ε-closure{q2}
= {q2}call it state C这样我们得到了
δ'(A, 0) = A
δ'(A, 1) = B
δ'(A, 2) = C部分DFA为：
文章图片
现在，我们将找到每个输入在状态B和C上的转换。
因此
δ'(B, 0) = ε-closure{δ((q1, q2), 0)}
= ε-closure{δ(q1, 0) ∪ δ(q2, 0)}
= ε-closure{?}
= ?δ'(B, 1) = ε-closure{δ((q1, q2), 1)}
= ε-closure{δ(q1, 1) ∪ δ(q2, 1)}
= ε-closure{q1}
= {q1, q2}i.e. state B itselfδ'(B, 2) = ε-closure{δ((q1, q2), 2)}
= ε-closure{δ(q1, 2) ∪ δ(q2, 2)}
= ε-closure{q2}
= {q2}i.e. state C itself这样我们得到了
δ'(B, 0) = ?
δ'(B, 1) = B
δ'(B, 2) = C部分过渡图将是
文章图片
现在我们将获得C的转换：
δ'(C, 0) = ε-closure{δ(q2, 0)}
= ε-closure{?}
= ?δ'(C, 1) = ε-closure{δ(q2, 1)}
= ε-closure{?}
= ?δ'(C, 2) = ε-closure{δ(q2, 2)}
= {q2}【自动机从ε NFA到DFA的转换】因此，DFA为
文章图片
由于A = {q0，q1，q2}，其中最终状态q2处于其中，因此A为最终状态。 B = {q1，q2}，其中状态q2处于其中，因此B也是最终状态。 C = {q2}，因此状态q2处于最终状态。
