个性化阅读
专注于IT技术分析

自动机从ε NFA到DFA的转换

点击下载

本文概述

非确定性有限自动机(NFA)是一种有限自动机,在某些情况下,当为当前状态提供特定输入时,机器将进入多个状态或不止一种状态。它可以包含εmove。它可以表示为M = {Q,∑,δ,q0,F}。

哪里

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}

因此,DFA为

由于A = {q0,q1,q2},其中最终状态q2处于其中,因此A为最终状态。 B = {q1,q2},其中状态q2处于其中,因此B也是最终状态。 C = {q2},因此状态q2处于最终状态。


赞(1)
未经允许不得转载:srcmini » 自动机从ε NFA到DFA的转换

评论 抢沙发

评论前必须登录!