non-deterministic finite automaton

A non-deterministic finite automaton (or NDFA) can be formally defined as a 5-tuple $(S,\Sigma,\delta,q_{0},F)$ , where

1.

$S$ is a non-empty finite set of states,
2.

$\Sigma$ is the alphabet (defining what set of input strings the automaton operates on),
3.

$\delta:S\times\Sigma\rightarrow\mathcal{P}(S)$ is a function called the transition function,
4.

$q_{0}\in Q$ is the starting state, and
5.

$F\subseteq S$ is a set of final (or accepting) states.

Some authors also relax the fourth condition by permitting multiple starting states (see remark below).

Note how this definition differs from that of a deterministic finite automaton (DFA) only by the definition of the transition function $\delta$ . Operation of the NDFA begins at $q_{0}$ , and movement from state to state is governed by the transition function $\delta$ .

The transition function takes the first symbol of the (remaining) input string and the current state as its input, and after the transition this first symbol is removed only if the transition is defined for a symbol in $\Sigma$ instead of $\lambda$ . Conceptually, all possible transitions from a current state are followed simultaneously (hence the non-determinism). Once every possible transition has been executed, the NDFA is halted. If any of the states reached upon halting are in $F$ for some input string, and the entire input string is consumed to reach that state, then the NDFA accepts that string.

An NDFA can be represented visually as a directed graph called the state diagram. Circular vertices denote states, and the set of directed edges, labelled by symbols in $\Sigma\cup\lambda$ , denotes $T$ . The starting state $q_{0}$ is usually denoted by an arrow pointing to it that points from no other vertex. States in $F$ are usually denoted by double circles.

NDFAs accept regular languages, and can be used to test whether any string in $\Sigma^{*}$ is in the language it represents. Given an NDFA $M$ , the language accepted by $M$ is denoted by $L(M)$ .

Consider the following regular language over the alphabet $\Sigma:=\left\{\verb.a.,\verb.b.\right\}$ (represented by the regular expression aa*b):

$\displaystyle\verb.<.S\verb.>.$	$\displaystyle\verb.::=.$	$\displaystyle\verb=a=\,A$
$\displaystyle\verb.<.A\verb.>.$	$\displaystyle\verb.::=.$	$\displaystyle\lambda\,B\,\verb.\|.\,\verb=a=\,A$
$\displaystyle\verb.<.B\verb.>.$	$\displaystyle\verb.::=.$	$\displaystyle\verb=b=$

This language can be represented by the NDFA with state diagram: