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

Given any Epsilon NFA (ε-NFA) , we can ﬁnd 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_{1}, p_{2},......, 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:-*

*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)**

## 1 Comments

Thanks a lot for such a simple explanation.. i just love it.

ReplyDeleteSubscribe Us and Thanks for visiting blog.