Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

Introduction to nondeterministic finite automaton

Ayesha Kanwal

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

nondeterministic finite automaton has one or more than one transition from one state to another or itself.

An NFA requires less space than a DFAdeterministic finite automaton for its construction. Moreover, a trap stateA state from which a transition can not escape. Also called a "dead state". is not required for an NFA.

Components of an NFA

Assume an NFA for a language L with the five tuples <Q,Σ,q0,δ,F><Q, Σ, q_0, δ, F> where

  • QQ is the finite set of states.
  • ΣΣ is the input symbols.
  • q0q_0 is the start state.
  • δδ is the transition function.
  • FF is the final state.

It is to be noted that δ:Q×Σ2Qδ: Q \times Σ \rightarrow 2 ^ Q. This means that the next possible states belong to the power set of QQ.

Example

The following is an example of an NFA, where q0q_0 is the start state.

g ENTRY q0 q0 ENTRY->q0 q4 q4 q0->q4   b q1 q1 q0->q1   a q2 q2 q0->q2   a q1->q0   a q3 q3 q2->q3   a q3->q0   b
NFA

RELATED TAGS

CONTRIBUTOR

Ayesha Kanwal
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring