Nondeterministic finite automaton

An NFA is represented formally by a 5-tuple, ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$, consisting of

• a finite set of states ${\displaystyle Q}$.
• a finite set of input symbols ${\displaystyle \Sigma }$.
• a transition function ${\displaystyle \delta }$ : ${\displaystyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$.
• an initial (or start) state ${\displaystyle q_{0}\in Q}$.
• a set of states ${\displaystyle F}$ distinguished as accepting (or final) states ${\displaystyle F\subseteq Q}$.

Here, ${\displaystyle {\mathcal {P}}(Q)}$ denotes the power set of ${\displaystyle Q}$.

Given an NFA ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$, its recognized language is denoted by ${\displaystyle L(M)}$, and is defined as the set of all strings over the alphabet ${\displaystyle \Sigma }$ that are accepted by ${\displaystyle M}$.

Loosely corresponding to the above informal explanations, there are several equivalent formal definitions of a string ${\displaystyle w=a_{1}a_{2}...a_{n}}$ being accepted by ${\displaystyle M}$:

• ${\displaystyle w}$ is accepted if a sequence of states, ${\displaystyle r_{0},r_{1},...,r_{n}}$, exists in ${\displaystyle Q}$ such that:
  1. ${\displaystyle r_{0}=q_{0}}$
  2. ${\displaystyle r_{i+1}\in \delta (r_{i},a_{i+1})}$, for ${\displaystyle i=0,\ldots ,n-1}$
  3. ${\displaystyle r_{n}\in F}$.

In words, the first condition says that the machine starts in the start state ${\displaystyle q_{0}}$. The second condition says that given each character of string ${\displaystyle w}$, the machine will transition from state to state according to the transition function ${\displaystyle \delta }$. The last condition says that the machine accepts ${\displaystyle w}$ if the last input of ${\displaystyle w}$ causes the machine to halt in one of the accepting states. In order for ${\displaystyle w}$ to be accepted by ${\displaystyle M}$, it is not required that every state sequence ends in an accepting state, it is sufficient if one does. Otherwise, i.e. if it is impossible at all to get from ${\displaystyle q_{0}}$ to a state from ${\displaystyle F}$ by following ${\displaystyle w}$, it is said that the automaton rejects the string. The set of strings ${\displaystyle M}$ accepts is the language recognized by ${\displaystyle M}$ and this language is denoted by ${\displaystyle L(M)}$.[5]^: 320[6]^: 54

• Alternatively, ${\displaystyle w}$ is accepted if ${\displaystyle \delta ^{*}(q_{0},w)\cap F\not =\emptyset }$, where ${\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}$ is defined recursively by:
  1. ${\displaystyle \delta ^{*}(r,\epsilon )=\{r\}}$ where ${\displaystyle \epsilon }$ is the empty string, and
  2. ${\displaystyle \delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)}$ for all ${\displaystyle x\in \Sigma ^{*},a\in \Sigma }$.

In words, ${\displaystyle \delta ^{*}(r,x)}$ is the set of all states reachable from state ${\displaystyle r}$ by consuming the string ${\displaystyle x}$. The string ${\displaystyle w}$ is accepted if some accepting state in ${\displaystyle F}$ can be reached from the start state ${\displaystyle q_{0}}$ by consuming ${\displaystyle w}$.[4]^: 21[7]^: 59

The above automaton definition uses a single initial state, which is not necessary. Sometimes, NFAs are defined with a set of initial states. There is an easy construction that translates an NFA with multiple initial states to an NFA with a single initial state, which provides a convenient notation.

An NFA-ε is represented formally by a 5-tuple, ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$, consisting of

• a finite set of states ${\displaystyle Q}$
• a finite set of input symbols called the alphabet ${\displaystyle \Sigma }$
• a transition function ${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow {\mathcal {P}}(Q)}$
• an initial (or start) state ${\displaystyle q_{0}\in Q}$
• a set of states ${\displaystyle F}$ distinguished as accepting (or final) states ${\displaystyle F\subseteq Q}$.

Here, ${\displaystyle {\mathcal {P}}(Q)}$ denotes the power set of ${\displaystyle Q}$ and ${\displaystyle \epsilon }$ denotes empty string.

For a state ${\displaystyle q\in Q}$, let ${\displaystyle E(q)}$ denote the set of states that are reachable from ${\displaystyle q}$ by following ε-transitions in the transition function ${\displaystyle \delta }$, i.e., ${\displaystyle p\in E(q)}$ if there is a sequence of states ${\displaystyle q_{1},...,q_{k}}$ such that

• ${\displaystyle q_{1}=q}$,
• ${\displaystyle q_{i+1}\in \delta (q_{i},\varepsilon )}$ for each ${\displaystyle 1\leq i<k}$, and
• ${\displaystyle q_{k}=p}$.

${\displaystyle E(q)}$ is known as the epsilon closure, (also ε-closure) of ${\displaystyle q}$.

The ε-closure of a set ${\displaystyle P}$ of states of an NFA is defined as the set of states reachable from any state in ${\displaystyle P}$ following ε-transitions. Formally, for ${\displaystyle P\subseteq Q}$, define ${\displaystyle E(P)=\bigcup \limits _{q\in P}E(q)}$.

Similar to NFA without ε-moves, the transition function ${\displaystyle \delta }$ of an NFA-ε can be extended to strings. Informally, ${\displaystyle \delta ^{*}(q,w)}$ denotes the set of all states the automaton may have reached when starting in state ${\displaystyle q\in Q}$ and reading the string ${\displaystyle w\in \Sigma ^{*}.}$ The function ${\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}$ can be defined recursively as follows.

• ${\displaystyle \delta ^{*}(q,\varepsilon )=E(q)}$, for each state ${\displaystyle q\in Q,}$ and where ${\displaystyle E}$ denotes the epsilon closure;

Informally: Reading the empty string may drive the automaton from state ${\displaystyle q}$ to any state of the epsilon closure of ${\displaystyle q.}$

• ${\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}$ for each state ${\displaystyle q\in Q,}$ each string ${\displaystyle w\in \Sigma ^{*}}$ and each symbol ${\displaystyle a\in \Sigma .}$

Informally: Reading the string ${\displaystyle w}$ may drive the automaton from state ${\displaystyle q}$ to any state ${\displaystyle r}$ in the recursively computed set ${\displaystyle \delta ^{*}(q,w)}$; after that, reading the symbol ${\displaystyle a}$ may drive it from ${\displaystyle r}$ to any state in the epsilon closure of ${\displaystyle \delta (r,a).}$

The automaton is said to accept a string ${\displaystyle w}$ if

${\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \emptyset ,}$

that is, if reading ${\displaystyle w}$ may drive the automaton from its start state ${\displaystyle q_{0}}$ to some accepting state in ${\displaystyle F.}$[4]^: 25

The state diagram for M

Let ${\displaystyle M}$ be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s. Note that 0 occurrences is an even number of occurrences as well.

In formal notation, let

$${\displaystyle M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})}$$

where

the transition relation ${\displaystyle \delta }$ can be defined by this state transition table:

${\displaystyle M}$ can be viewed as the union of two DFAs: one with states ${\displaystyle \{S_{1},S_{2}\}}$ and the other with states ${\displaystyle \{S_{3},S_{4}\}}$. The language of ${\displaystyle M}$ can be described by the regular language given by this regular expression ${\displaystyle (1^{*}01^{*}0)^{*}\cup (0^{*}10^{*}1)^{*}}$. We define ${\displaystyle M}$ using ε-moves but ${\displaystyle M}$ can be defined without using ε-moves.

To show NFA-ε is equivalent to NFA, first note that NFA is a special case of NFA-ε, so it remains to show for every NFA-ε, there exists an equivalent NFA.

Given an NFA with epsilon moves ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F),}$ define an NFA ${\displaystyle M'=(Q,\Sigma ,\delta ',q_{0},F'),}$ where

${\displaystyle F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}}$

and

${\displaystyle \delta '(q,a)=\delta ^{*}(q,a)}$ for each state ${\displaystyle q\in Q}$ and each symbol ${\displaystyle a\in \Sigma ,}$ using the extended transition function ${\displaystyle \delta ^{*}}$ defined above.

One has to distinguish the transition functions of ${\displaystyle M}$ and ${\displaystyle M',}$ viz. ${\displaystyle \delta }$ and ${\displaystyle \delta ',}$ and their extensions to strings, ${\displaystyle \delta }$ and ${\displaystyle \delta '^{*},}$ respectively. By construction, ${\displaystyle M'}$ has no ε-transitions.

One can prove that ${\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}$ for each string ${\displaystyle w\neq \varepsilon }$, by induction on the length of ${\displaystyle w.}$

Based on this, one can show that ${\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}}$ if, and only if, ${\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \{\},}$ for each string ${\displaystyle w\in \Sigma ^{*}:}$

• If ${\displaystyle w=\varepsilon ,}$ this follows from the definition of ${\displaystyle F'.}$
• Otherwise, let ${\displaystyle w=va}$ with ${\displaystyle v\in \Sigma ^{*}}$ and ${\displaystyle a\in \Sigma .}$

From ${\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}$ and ${\displaystyle F\subseteq F',}$ we have

$${\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};}$$

we still have to show the "${\displaystyle \Rightarrow }$" direction.

• If ${\displaystyle \delta '^{*}(q_{0},w)}$ contains a state in ${\displaystyle F'\setminus \{q_{0}\},}$ then ${\displaystyle \delta ^{*}(q_{0},w)}$ contains the same state, which lies in ${\displaystyle F}$.
• If ${\displaystyle \delta '^{*}(q_{0},w)}$ contains ${\displaystyle q_{0},}$ and ${\displaystyle q_{0}\in F,}$ then ${\displaystyle \delta ^{*}(q_{0},w)}$ also contains a state in ${\displaystyle F,}$ viz. ${\displaystyle q_{0}.}$
• If ${\displaystyle \delta '^{*}(q_{0},w)}$ contains ${\displaystyle q_{0},}$ and ${\displaystyle q_{0}\not \in F,}$ then the state in ${\displaystyle E(q_{0})\cap F}$ must be in ${\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}$[4]^: 26–27

Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA.