'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Dec 30, 2023
Medium

Conversion of Epsilon - NFA to NFA

Author Riya
2 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Conversion of Epsilon - NFA to NFA

Introduction 

This article will discuss how to convert epsilon - NFA to NFA. Before moving to the conversion of epsilon - NFA to NFA, let’s recall epsilon - NFA and NFA.

To know about NFA and epsilon NFA, we need to know about Finite Automata.


Finite Automata are a collection of five tuples used to recognize patterns. They take strings of symbols as input and have a set of states and rules to move from one state to another depending on the input strings of symbols. 


Now let’s see what epsilon - NFA and NFA is.

Also See, Moore Machine

What is the epsilon in NFA?

NFA(Non-deterministic Finite Automata) is a finite automaton containing zero, one, or more moves from a given state on a given input symbol. Epsilon NFA is an NFA having epsilon/NULL moves.

Read About - Simplification of CFG

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

epsilon nfa

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 = q0

dest = q1

epsilon move

Figure 2



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

Here, dest = q1

All the moves starting from q1 are:

epsilon destination

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 = q0 and dest = q1

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:

Conversion of Epsilon - NFA to NFA

Figure 4


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

Here, dest = q1

As q1 is a final state, q0 will also be converted to a final state

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

Epsilon final state

Figure 5

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

Here, src = q0

As q0 is a start state, q1 will also be converted to a start state

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

start state in epsilon

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: 

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.

Previous article
Conversion from NFA to DFA
Next article
DFA Minimization
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass