Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Formal definition of Non-Deterministic Finite Automata
3.
Graphical Representation of an NFA
3.1.
Example 1: Simple NFA
3.2.
Example 2: NFA with Epsilon Transitions
4.
Need for Non-Deterministic Finite Automata
5.
Acceptance by Non-Deterministic Finite Automata
6.
DFA vs NDFA
7.
Frequently Asked Questions
7.1.
What is a non-deterministic finite automata?
7.2.
What is the DFA and NFA?
7.3.
Why is NFA used?
7.4.
Which is more powerful, NFA or DFA?
7.5.
What is the application of non-deterministic finite automata(NFA)?
7.6.
What is a nondeterministic finite automaton to regular expression?
8.
Conclusion
Last Updated: Jul 6, 2024
Easy

Non-Deterministic Finite Automata

Author Shivani Singh
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In computer science and theoretical computation, automata theory stands as a foundational concept that helps us understand how machines process information. Among the various types of automata, Non-Deterministic Finite Automata (NFA) hold a special place due to their intriguing properties and applications.

Since NFAs have fewer constraints than DFAs, they can make complex Automata easier to understand and depict in a diagram. We can define the non-deterministic finite automaton as a finite automaton variant with two characteristics:

  • ε-transition: state transition can be made without reading a symbol; and 
  • Nondeterminism: state transition can have zero or more than one possible value.
Non-Deterministic Finite Automata

However, the above said features do not give NFA any additional power. When it comes to power, NFA and DFA are equatable.

Due to the above additional features, NFA has a different transition function, rest is the same as DFA.

Let us understand the concept of NFA with an example: 

One thing to keep in mind is that in NFA if any path for an input string leads to a final state, the input string is accepted. As shown in the above excerpt, there are different paths for the input string "00" inside the preceding NFA. Since one of the paths leads to a final state, the above NFA accepts "00."

Also See, Moore Machine

Formal definition of Non-Deterministic Finite Automata

The formal definition of NFA, like that of DFA, is: (Q, 𝚺, δ, q0, F), where 

  • Q is a finite set of states.
  • 𝚺 is a finite set of all alphabet symbols.
  • δ: Q x 𝚺 → Q is the transition function from state to state.
  • q0 ∈ Q is the starting state, and the starting state must be in the set Q 
  • F ⊆ Q is the set of accepted states, all of which must be in the set Q.

 

The only difference between an NFA and a DFA in terms of formal definition is that an NFA requires to include the empty string (ε) in the delta function along with the other symbols.

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

Graphical Representation of an NFA

Non-Deterministic Finite Automata (NFA) are best understood through visual representations that depict states, transitions, and the concept of non-determinism. Let's break down the graphical representation of an NFA with examples.

An NFA is composed of:

  1. States: Represented by circles.
  2. Transitions: Arrows between states indicating how the automaton moves from one state to another based on input symbols.
  3. Start State: The initial state, often depicted with an incoming arrow pointing to it.
  4. Accept States: States that indicate acceptance of the input string, usually represented by double circles.
  5. Non-Deterministic Transitions: Multiple transitions for a single input symbol from a given state.

Example 1: Simple NFA

Consider an NFA that accepts the language of strings ending with 'a' over the alphabet {a, b}.

  1. States: q0 (start state), q1 (accept state)
  2. Transitions:
    • From q0 to q1 on input 'a'
    • From q0 to q0 on input 'b'
    • From q1 to q1 on input 'a' or 'b'

Graphically, it looks like this:

    a
(q0) ---> (q1)
  |         /|\
  |______   |
         |  |
         b  b

In this NFA:

  • Starting at q0, on input 'a', it transitions to q1.
  • On input 'b', it remains in q0.
  • At q1, it loops on both 'a' and 'b'.

Example 2: NFA with Epsilon Transitions

Consider an NFA that accepts strings containing the substring "ab" over the alphabet {a, b}.

  1. States: q0 (start state), q1, q2 (accept state)
  2. Transitions:
    • From q0 to q1 on input 'a'
    • From q1 to q2 on input 'b'
    • Epsilon transition from q0 to q2

Graphically, it looks like this:

    a       b
(q0) ---> (q1) ---> (q2)
   \                /
    \______________/
       ε

In this NFA:

  • Starting at q0, on input 'a', it transitions to q1.
  • From q1, on input 'b', it transitions to q2.
  • There is also an epsilon (ε) transition directly from q0 to q2, meaning the NFA can jump to q2 without consuming any input.

Need for Non-Deterministic Finite Automata

There is a corresponding DFA for every NFA that accepts the same language. If the NFA has n states, the DFA could have Θ(2n) states. So we work with NFAs because they are likely to be much smaller than DFAs. 

Constructing NFA for a given string is easier than constructing DFA for that particular string. In other words, NFA can reduce the complexities of the mathematical work needed to establish many important properties in computation theory. NFAs, for example, make it much easier to prove regular language closure properties than DFAs.

Image source: NFA

Acceptance by Non-Deterministic Finite Automata

A Non-Deterministic Finite Automata acknowledges the input string if there is a set of transitions that leads to the accepted state. As an outcome, whereas one accepting branch is sufficient for the overall NFA to accept the string, every branch must reject for the overall NFA to reject. 

Yes, you are thinking right. This Non-Deterministic Finite Automata accepts any binary string that contains 00 or 11 as a substring. 

Also See, Symbol Table Operations

The transition table for the above NFA is as follows

Present StateNext state for input 0Next state for input 1
→AA, BA, C
BDNil
CNilD
*DDD

Also read - Arden's theorem

Let us change the question and design an NFA that accepts all binary strings that end with 101.

NFA

Here is the required NFA. from the question, it's clear that the condition only lies in the ending of the string, i,e, it should only end with 101. The starting string does not matter. So we are passing the string 0,1 in the starting state and after that 1, 0, 1 is passed to the coming states.

The transition table for the above NFA is given below

Present StateNext state for input 0Next state for input 1
→AAA, B
BCNil
CNilD
*DNilNil


Also see, Turing Machine in TOC.

DFA vs NDFA

Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) are both fundamental concepts in automata theory. While they share similarities in their purpose of recognizing patterns and languages, there are key differences that distinguish them.

ParameterDFANFA
DeterminismEvery state has exactly one transition per input symbol.States can have zero, one, or multiple transitions for a given input symbol.
Transition Functionδ: Q × Σ → Qδ: Q × Σ → P(Q) (where P(Q) is the power set of Q)
Epsilon (ε) TransitionsNot allowedAllowed
State ComplexityGenerally requires more states to represent certain languages.Can often represent the same language with fewer states.
ImplementationEasier to implement due to determinism.More complex to implement due to non-determinism.
SimulationCan be simulated by an NFA without modification.Requires conversion to DFA for simulation on deterministic machines.
AcceptanceAccepts input if there is a unique sequence of transitions leading to an accept state.Accepts input if there exists at least one sequence of transitions leading to an accept state.
BacktrackingDoes not require backtracking.Can use backtracking to explore multiple transitions.
Practical UseWidely used in lexical analysis, text parsing, etc.Used in more theoretical contexts and where non-determinism provides a clearer solution.

See More, DFA minimization

Frequently Asked Questions

What is a non-deterministic finite automata?

A Non-Deterministic Finite Automata (NFA) is a type of automaton where multiple transitions for a single input are possible from any given state.

What is the DFA and NFA?

A Deterministic Finite Automata (DFA) has one transition per input symbol per state, while a Non-Deterministic Finite Automata (NFA) can have multiple transitions for the same input.

Why is NFA used?

NFA is used for its simplicity in construction and ability to express certain languages with fewer states compared to DFA.

Which is more powerful, NFA or DFA?

Both NFA and DFA have the same computational power, capable of recognizing the same class of regular languages.

What is the application of non-deterministic finite automata(NFA)?

Non-deterministic finite automata are used in various applications, including lexical analysis in compiler design, pattern matching in text processing, and natural language processing tasks like tokenization and parsing.

What is a nondeterministic finite automaton to regular expression?

The conversion from a non-deterministic finite automaton (NFA) to a regular expression involves creating an equivalent regular expression that represents the same language as the NFA. This conversion is useful in simplifying regular expressions and optimizing pattern matching algorithms.

Conclusion

To conclude, we talked about non-deterministic finite automata. We also learned about the fundamental differences between NFA and DFA. We mentioned the importance of non-deterministic finite automata. And in which condition, any string is accepted by NFA. Finally, we looked at the major differences between NFA and DFA in aspects of detailing.

Check out this article - Converting NFA to DFA

We believe that this blog has assisted you to learn more about NFA. You can check out our DFA article here. This isn't the end; if you're curious to learn more, check out our other theory of computation articles here. Do upvote our blog to help other ninjas grow. 

Previous article
Deterministic Finite Automata or DFA
Next article
Conversion from NFA to DFA
Live masterclass