Introduction to nondeterministic finite automaton

Overview

A 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, Σ, q_0, δ, F>$ where

• $Q$ is the finite set of states.
• $Σ$ is the input symbols.
• $q_0$ is the start state.
• $δ$ is the transition function.
• $F$ is the final state.

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

Example

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