Conversion of Epsilon - NFA to NFA

Steps to convert epsilon - NFA to NFA

This section will cover the steps to convert epsilon - NFA to NFA.

 Also read - Arden's theorem

Let’s take an example of Q (a finite set of states) and understand the below-mentioned steps to convert epsilon - NFA to NFA by removing all the epsilon moves in it:

Given Q:

Figure 1

Step 1: Consider two states having epsilon moves between them. Take two vertices, ‘src’ and ‘dest,’ such that

src = Starting state of the epsilon move

dest = Destination state of the epsilon move

In Q, we can see an epsilon move from state q0 to q1 that needs to be removed, so consider them.

src = q₀

dest = q₁

Figure 2

Step 2: Find all the moves starting from ‘dest’. 

Here, dest = q₁

All the moves starting from q₁ are:

Figure 3

Step 3: Remove the epsilon move and copy all the above-found moves starting from ‘dest’ to start from ‘src’ with the same input.

Here, src = q₀ and dest = q₁

After removing the epsilon move and creating the copy of all the moves starting from q1 to start from q0 with the same input, Q will be converted to:

Figure 4

Step 4:   If state ‘dest’ is a final state, then make the state ‘src’ also a final state.

Here, dest = q₁

As q₁ is a final state, q₀ will also be converted to a final state

After converting q₀ to a final state, Q will be converted to:

Figure 5

Step 5:  If state ‘src’ is a start state, then make the state ‘dest’ also a final state.

Here, src = q₀

As q₀ is a start state, q₁ will also be converted to a start state

After converting q₁ to a start state, Q will be converted to:

Figure 6

Step 6:  Repeat steps 1-4 for all the remaining epsilon moves. If there is no epsilon move left, then stop.

Here we can see that there are no epsilon moves left. So, given Q shown in ‘figure 1’ will be converted to ‘figure 6’ after removing all the epsilon moves in the process of conversion of epsilon - NFA to NFA.

Also see, Turing Machine in TOC.

Frequently Asked Questions

What is epsilon in NFA?

In NFA (nondeterministic finite automata), the symbol "epsilon" (ε) refers to a transition that doesn't require any input or an empty string. Essentially, it allows an NFA to change from one state to another without consuming any input.

What is epsilon closure of an NFA?

In NFA, the epsilon closure (ε-closure) is a set of states reachable from a specific state through epsilon transitions that don't consume any input. It includes the starting state and all states that can be reached via epsilon transitions from that state.

How do you convert epsilon NFA to NFA?

To convert an epsilon NFA (ε-NFA) to an NFA, remove all epsilon transitions first. Create new transitions for every potential transition combination. Create a new transition table and set of accepted states for the converted NFA.

What is epsilon in DFA?

Epsilon(ε) in DFA (deterministic finite automata) signifies a non-existent input symbol or a null transition. Epsilon transitions are not permitted in DFA, unlike in NFA (nondeterministic finite automata). As a result, epsilon transitions are inapplicable in DFA.

Conclusion

This article discussed the method of conversion of epsilon - NFA to NFA. We also briefly discussed what epsilon is in NFA and some frequently asked questions.

If you think that this blog helped you share it with your friends! 

Recommended Readings: 

• DFA minimization
• Conversion of NFA to DFA
• Non-Deterministic Finite Automata
• Deterministic Finite Automata
• Symbol Table Operations
• Difference Between Analog and Digital Computer

To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, All the best for your future endeavours, and Keep Coding.