'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

# Nondeterministic Finite Automata

yuvatimankar
1 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
Earn badges and level up

## Introduction

Nondeterministic means where the transition from a state can be to multiple next states for each input symbol. It has been observed that NFA is easier to construct than DFA. Every NFA is not DFA, but not each NFA can be translated to DFA.

In Nondeterministic automation, we cannot determine the same state the machine moves.

Every NFA can be converted to DFA, but every NFA is not DFA. NFA is the same as DFA, but with two exceptions, It contains multiple states, and it contains Îµ transitions,Îµ here simply means empty string.

## Definition of an NFA

NFA also has five tuples as DFA, but different transition functions, as shown below:

Q, âˆ‘, Î´, q0, F

Where,

• Q represents the finite set of states
• âˆ‘ represents a finite set of symbols known as alphabets
• Î´ represents the transition function where Î´: Q x âˆ‘ â†’2Q
• Q0 is an initial state
• F is a final state

Read About - Symbol Table Operations And Cross Compiler

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

## Graphical representation of NFA

An NFA is represented by digraphs called state diagrams.

• Vertices represent the state.
• The arc, which is labeled by input direction, shows the transition.
• An arrow denotes the initial state.
• A double circle represents the final state.

## Regular Expressions

A regular expression can be defined as a language accepted by finite Automata. It is used to match character combinations in a string. The string searching algorithm uses a regular expression to find the operations on a string.

Also see, Introduction to Automata Theory

## Converting regular expression to an NFA

We will use Thompson's construction method to convert the regular expression to an NFA. Regular expressions and NFA are both representations of formal language. Text-processing utilities use regular expressions to describe advanced search patterns, but NFA is better suited for execution on a computer.

Thompson is a method for converting regular expressions to their respective NFA diagrams. Thompson construction consists of 5 rules:

Rule1:

An empty expression will be converted to :

Rule 2:

A symbol will be converted to :

Rule 3:

The union expression is converted to :

Rule 4:

The concatenation expression is converted to :

Rule 5:

The Kleene star expression is converted to:

Example:

• Create NFA for regular expression ab:

• Crete NFA for regular expression a + b :
• Create NFA for regular expression a* :

• Create NFA for regular expression ( a + b )* :

Check out this article - Converting NFA to DFA

## Frequently Asked Questions

### What is NFA?

NFA stands for nondeterministic automata. A finite automaton is called an NFA when multiple paths exist for specific input from the current state to the next state.

### What do you mean by automata?

Automata is a relatively self-operating mechanism or machine designed to follow a predetermined sequence of instructions automatically.

### What are the properties of NFA?

An NFA can have zero, one, or multiple transitions corresponding to a particular symbol.

## Conclusion

In this article, we studied Nondeterministic finite Automata(NFA). We saw the definitions of NFA, regular expressions, and how to convert regular expressions to NFA. We have used Thompson's construction method to convert regular expressions to NFA.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
Earn badges and level up
Live masterclass