'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

Riya
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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.

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.

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

dest = q1

Figure 2

Step 2: Find all the moves starting from â€˜destâ€™.

Here, dest = q1

All the moves starting from q1 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 = 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:

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:

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:

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.

### 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!

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.

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems