Nondeterministic finite automaton

In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if

• each of its transitions is uniquely determined by its source state and input symbol, and
• reading an input symbol is required for each state transition.

A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to a NFA that is not a DFA, but not in this article.

Using the subset construction algorithm, each NFA can be translated to an equivalent DFA, i.e. a DFA recognizing the same formal language. Like DFAs, NFAs only recognize regular languages.

NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings.

NFAs have been generalized in multiple ways, e.g., nondeterministic finite automaton with ε-moves, finite state transducers, pushdown automata, alternating automata, ω-automata, and probabilistic automata. Besides the DFAs, other known special cases of NFAs are unambiguous finite automata (UFA) and self-verifying finite automata (SVFA).

Informal introduction

An NFA, similar to a DFA, consumes a string of input symbols. For each input symbol, it transitions to a new state until all input symbols have been consumed. Unlike a DFA, it is non-deterministic, i.e., for some state and input symbol, the next state may be nothing or one or two or more possible states. Thus, in the formal definition, the next state is an element of the power set of the states, which is a set of states to be considered at once. The notion of accepting an input is similar to that for the DFA. When the last input symbol is consumed, the NFA accepts if and only if there is some set of transitions that will take it to an accepting state. Equivalently, it rejects, if, no matter what transitions are applied, it would not end in an accepting state.

Formal definition

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

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

Here, $P(Q)$ denotes the power set of $Q$. Let $w=a_{1}a_{2}...a_{n}$ be a word over the alphabet $\Sigma$. The automaton $M$ accepts the word $w$ if a sequence of states, $r_{0},r_{1},...,r_{n}$, exists in $Q$ with the following conditions:

1. $r_{0}=q_{0}$
2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$, for $i=0,\ldots ,n-1$
3. $r_{n}\in F$.

In words, the first condition says that the machine starts in the start state $q_{0}$. The second condition says that given each character of string $w$, the machine will transition from state to state according to the transition function $\Delta$. The last condition says that the machine accepts $w$ if the last input of $w$ causes the machine to halt in one of the accepting states. In order for $w$ to be accepted by $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 $q_{0}$ to a state from $F$ by following $w$, it is said that the automaton rejects the string. The set of strings $M$ accepts is the language recognized by $M$ and this language is denoted by $L(M)$.

We can also define $L(M)$ in terms of $\Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)$ such that:

1. $\Delta ^{*}(r,\epsilon )=\{r\}$ where $\epsilon$ is the empty string, and
2. If $x\in \Sigma ^{*},a\in \Sigma$, and $\Delta ^{*}(r,x)=\{r_{1},r_{2},...,r_{k}\}$ then $\Delta ^{*}(r,xa)=\Delta (r_{1},a)\cup ...\cup \Delta (r_{k},a)$.

Now $L(M)=\{w|\Delta ^{*}(q_{0},w)\cap F\not =\emptyset \}$.

Note that there is 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 a NFA with multiple initial states to a NFA with single initial state, which provides a convenient notation.

For a more elementary introduction of the formal definition see automata theory.

Example

The state diagram for M. It is not deterministic since in state p reading a 1 can lead to p or to q.

Let $M$ be an NFA, with a binary alphabet, that determines if the input ends with a 1.

In formal notation, let $M=(\{p,q\},\{0,1\},\Delta ,p,\{q\})$ where the transition function $\Delta$ can be defined by this state transition table:

Input State	0	1
$p$	$\{p\}$	$\{p,q\}$
$q$	$\emptyset$	$\emptyset$

Note that $\Delta (p,1)$ has more than one state, therefore $M$ is nondeterministic. The language of $M$ can be described by the regular language given by the regular expression (0|1)*1. Some possible state sequences for the input word "1011" are:

Input:		1		0		1		1
State sequence 1:	p		q		?
State sequence 2:	p		p		p		q		?
State sequence 3:	p		p		p		p		q

The word is accepted by $M$ since state sequence 3 satisfies the above definition; it doesn't matter that sequences 1 and 2 fail to do so. In contrast, the word "10" is rejected by $M$, since there is no way to reach the only accepting state, $q$, by reading the final 0 symbol or by an ε-transition.

Equivalence to DFA

A Deterministic finite automaton (DFA) can be seen as a special kind of NFA, in which for each state and alphabet, the transition function has exactly one state. Thus, it is clear that every formal language that can be recognized by a DFA can be recognized by a NFA.

Conversely, for each NFA, there is a DFA such that it recognizes the same formal language. The DFA can be constructed using the powerset construction.

This result shows that NFAs, despite their additional flexibility, are unable to recognize languages that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to 2ⁿ states, which sometimes makes the construction impractical for large NFAs.

NFA with ε-moves

Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA. This automaton replaces the transition function with the one that allows the empty string ε as a possible input. The transitions without consuming an input symbol are called ε-transitions. In the state diagrams, they are usually labeled with the Greek letter ε. ε-transitions provide a convenient way of modeling the systems whose current states are not precisely known: i.e., if we are modeling a system and it is not clear whether the current state (after processing some input string) should be q or q', then we can add an ε-transition between these two states, thus putting the automaton in both states simultaneously.

Formal definition

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

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

Here, $P(Q)$ denotes the power set of $Q$ and ε denotes empty string.

ε-closure of a state or set of states

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

• $q_{1}=q$,
• $q_{i+1}\in \Delta (q_{i},\epsilon )$ for each 1 ≤ i < k, and
• $q_{k}=p$.

$E(q)$ is known as the ε-closure of $q$.

ε-closure is also defined for a set of states. The ε-closure of a set of states, $P$, of an NFA is defined as the set of states reachable from any state in $P$ following ε-transitions. Formally, for $P\subseteq Q,E(P)=$∪_q∈P E(q).

Accepting states

Let $w=a_{1}a_{2}...a_{n}$ be a word over the alphabet $\Sigma$. The automaton $M$ accepts the word $w$ if a sequence of states, $r_{0},r_{1},...,r_{n}$, exists in $Q$ with the following conditions:

1. $r_{0}\in E(q_{0})$
2. $r_{i+1}\in E(r')$ where $r'\in \Delta (r_{i},a_{i+1})$ for each $i=0,...,n-1$, and
3. $r_{n}\in F$.

In words, the first condition says that the machine starts at the state that is reachable from the start state $q_{0}$ via ε-transitions. The second condition says that after reading $a_{i}$, the machine takes a transition of $\Delta$ from $r_{i}$ to $r'$, and then takes any number of ε-transitions according to $\Delta$ to move from $r'$ to $r_{i+1}$. The last condition says that the machine accepts $w$ if the last input of $w$ causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings $M$ accepts is the language recognized by $M$ and this language is denoted by $L(M)$.

Example

The state diagram for M

Let $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 $M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta ,S_{0},\{S_{1},S_{3}\})$ where the transition relation $\Delta$ can be defined by this state transition table:

Input State	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

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

Equivalence to NFA

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.

Let $A=(Q,\Sigma ,\Delta ,q_{0},F)$ be a NFA-ε. The NFA $A'=(Q,\Sigma ,\Delta ',E(q_{0}),F)$ is equivalent to $A$, where for each $a\in \Sigma$ and $q\in Q$, $\Delta '(q,a)=E(\Delta (q,a))$.

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

Closure properties

Composed NFA accepting the union of the languages of some given NFAs N(s) and N(t). For an input word w in the language union, the composed automaton follows an ε-transition from q to the start state (left colored circle) of an appropriate subautomaton — N(s) or N(t) — which, by following w, may reach an accepting state (right colored circle); from there, state f can be reached by another ε-transition. Due to the ε-transitions, the composed NFA is properly nondeterministic even if both N(s) and N(t) were DFAs; vice versa, constructing a DFA for the union language (even of two DFAs) is much more complicated.

NFAs are said to be closed under a (binary/unary) operator if NFAs recognize the languages that are obtained by applying the operation on the NFA recognizable languages. The NFAs are closed under the following operations.

• Union (cf. picture)
• Intersection
• Concatenation
• Negation
• Kleene closure

Since NFAs are equivalent to nondeterministic finite automaton with ε-moves (NFA-ε), the above closures are proved using closure properties of NFA-ε. The above closure properties imply that NFAs only recognize regular languages.

NFAs can be constructed from any regular expression using Thompson's construction algorithm.

Properties

The machine starts in the specified initial state and reads in a string of symbols from its alphabet. The automaton uses the state transition function Δ to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an NFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in". If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.

The set of all strings accepted by an NFA is the language the NFA accepts. This language is a regular language.

For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language. Therefore, it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the powerset construction, which may lead to an exponential rise in the number of necessary states. For a formal proof of the powerset construction, please see the Powerset construction article.

Implementation

There are many ways to implement a NFA:

• Convert to the equivalent DFA. In some cases this may cause exponential blowup in the number of states.
• Keep a set data structure of all states which the NFA might currently be in. On the consumption of an input symbol, unite the results of the transition function applied to all current states to get the set of next states; if ε-moves are allowed, include all states reachable by such a move (ε-closure). Each step requires at most s² computations, where s is the number of states of the NFA. On the consumption of the last input symbol, if one of the current states is a final state, the machine accepts the string. A string of length n can be processed in time O(ns²), and space O(s).
• Create multiple copies. For each n way decision, the NFA creates up to $n-1$ copies of the machine. Each will enter a separate state. If, upon consuming the last input symbol, at least one copy of the NFA is in the accepting state, the NFA will accept. (This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)
• Explicitly propagate tokens through the transition structure of the NFA and match whenever a token reaches the final state. This is sometimes useful when the NFA should encode additional context about the events that triggered the transition. (For an implementation that uses this technique to keep track of object references have a look at Tracematches.)

Application of NFA

NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa. The establishment of such equivalence is important and useful. It is useful because constructing an NFA to recognize a given language is sometimes much easier than constructing a DFA for that language. It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation. For example, it is much easier to prove closure properties of regular languages using NFAs than DFAs.

See also

• Deterministic finite automaton
• Two-way nondeterministic finite automaton
• Pushdown automaton
• Turing Machine

References

• M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp. 115–125.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. (see section 1.2: Nondeterminism, pp. 47–63.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 2.)