Eliminating Epsilon transition (ε-Transitions) | Conversion of Epsilon-NFA to DFA | Conversion of Epsilon-NFA to NFA | Theory Of Computation (TOC)

Theory Of Computation (TOC) | Eliminating Epsilon Transition(ε-Transitions):

Given any Epsilon NFA (ε-NFA) , we can find a DFA D that accepts the same language as E. The construction is close to the subset construction, as the states of D are subsets of the states of E. The only difference is that dealing with ε-transitions, which can be done by using ε-closure.


Epsilon NFA (ε-NFA) - DFA:
Let E = (Q_E,∑, 𝛿_E,q_o, F_E) is ε-NFA. The DFA equivalent to given ε-NFA is constructed as:

D = (Q_D,∑, 𝛿_D,q_D, F_D)

Where,
Q_D= set of subsets of Q_E i.e Q_D ⊆ 2ᣔQ_E
q_D=ε-closure(q_o)
F_D = set of states that contains at least one accepting state of E.

i.e. F_D= {S|S is in q_D and S∩F_E∉φ}.

𝛿_D (S, a) is computed, for all a in ∑ and sets S in Q_D by:

• Let 𝛿_cap(q, x) = {p₁, p₂,......, p_k} i.e. p_i ’s are the states that can be reached from q following path labeled x which can end with many ε & can have many ε.
• Compute

• Then,

For Example:

Conversion of Epsilon-NFA to DFA

Given an ε-NFA as:

Transition Diagram:

ε-NFA —NFA:

Let E = (Q_E,∑, 𝛿_E,q_o, F_E) is ε-NFA. The NFA equivalent to given ε-NFA is constructed as:

N = (Q_N,∑, 𝛿_N,q_N, F_N)

• Start state of NFA =Start state of ε-NFA i.e. q_N= q_o
• Q_N= set of subsets of Q_E i.e Q_N ⊆ QE
• For any state q  ∈ Q_N and a ∈ Σ:

𝛿_N(q, a) = ε-closure (𝛿_E(ε- closure(q), a))

• F_N= { q ∈ Q_N: ε- closure(q) ∩F_E≠φ}

For Example:

Given an ε-NFA as:

Transition Table:

Transition Diagram:

Related Posts:-

Automata Theory | Deterministic Finite Automata (DFA) | Transition Table | Transition Diagrams | Language of DFA | Theory Of Computation (TOC)

Non Deterministic Finite Automata | Language of NFA | Extended transition function of NFA | Theory Of Computation (TOC)

Moore and Mealy Machine | Theory Of Computation (TOC)

NFA with Epsilon-Transition (ε-NFA) | Epsilon-Closure (ε-Closure) of a state | Extended Transition Function of ε-NFA | Theory Of Computation (TOC)