'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

Author yuvatimankar
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Compiler Design

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.

Also See, Specifications of Tokens in Compiler Design

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.

 

Illustration Image NFA

 

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 :

Illustration Image

 

Rule 2:

A symbol will be converted to :

 

Illustration Image

Rule 3:

The union expression is converted to :

Illustration Image

 

Rule 4:

The concatenation expression is converted to :

 

Illustration Image

Rule 5:

The Kleene star expression is converted to:

Illustration Image


Example:

  • Create NFA for regular expression ab:
Illustration Image

 

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

 

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

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!

Previous article
Lex in Compiler Design
Next article
Deterministic Finite Automata
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass