'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
Easy

Non-Deterministic Finite Automata

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

Introduction

An NFA or NDFA, like a DFA, is a state machine made up of states and transitions that can accept or reject a finite string. We already know that Deterministic Finite Automata and Non-Deterministic Finite Automata are the two types of Finite Automata Machines. In addition, we must use circles to represent states and directed arrows to represent transitions, just like a DFA. But what's the distinction?

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.

 

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

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. 

Any guesses what the following NFA accepts?

Common try it, it's not that tough.

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 State Next state for input 0 Next state for input 1
→A A, B A, C
B D Nil
C Nil D
*D D D

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 State Next state for input 0 Next state for input 1
→A A A, B
B C Nil
C Nil D
*D Nil Nil


Also see, Turing Machine in TOC.

Differences between Deterministic Finite Automata and Non-Deterministic Finite Automata

  1. A DFA can only have one transition for each symbol that exits the state. An NFA, on the other hand, can have multiple transitions for the same symbol from the same state.
  2. Non-Deterministic Finite Automata does not need the requirement to have a transition for each symbol. 
  3. An empty string can have a transition in NFA. A DFA cannot transition on an empty string since it is an invalid transition, but an NFA can.
  4. Backtracking is allowed in DFA, whereas in NFA it's not always possible.

 

See More, DFA minimization

Frequently Asked Questions

What Is Non-determinism And Determinism in Automata and What Is The Difference Between Them?

Determinism refers to the fact that our computational model (machine) knows what to do in the face of any given input. Our machine may or may not know if it has to do with all possible inputs due to nondeterminism. A  non-deterministic machine can't be implemented (used) on a computer unless it's converted into a deterministic machine.

What is non-deterministic finite automata explain?

A non-deterministic finite automaton (NFA) is a theoretical model in automata theory. It consists of states, transitions, and input symbols, where multiple transitions from a state with the same input are allowed, making it non-deterministic.

What is the application of non-deterministic finite automata?

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

Happy Coding!

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