In automata theory, a finitestate machine is called a deterministic finite automaton (DFA), if
A nondeterministic finite automaton (NFA), or nondeterministic finitestate 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 an 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.^{[1]} Like DFAs, NFAs only recognize regular languages.
NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott,^{[2]} 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. Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton).
NFAs have been generalized in multiple ways, e.g., nondeterministic finite automata with εmoves, finitestate transducers, pushdown automata, alternating automata, ωautomata, and probabilistic automata. Besides the DFAs, other known special cases of NFAs are unambiguous finite automata (UFA) and selfverifying finite automata (SVFA).
There are two ways to describe the behavior of an NFA, and both of them are equivalent. The first way makes use of the nondeterminism in the name of an NFA. For each input symbol, the NFA transitions to a new state until all input symbols have been consumed. In each step, the automaton nondeterministically "chooses" one of the applicable transitions. If there exists at least one "lucky run", i.e. some sequence of choices leading to an accepting state after completely consuming the input, it is accepted. Otherwise, i.e. if no choice sequence at all can consume all the input^{[3]} and lead to an accepting state, the input is rejected.^{[4]}^{: 19 }^{[5]}^{: 319 }
In the second way, the NFA consumes a string of input symbols, one by one. In each step, whenever two or more transitions are applicable, it "clones" itself into appropriately many copies, each one following a different transition. If no transition is applicable, the current copy is in a dead end, and it "dies". If, after consuming the complete input, any of the copies is in an accept state, the input is accepted, else, it is rejected.^{[4]}^{: 19–20 }^{[6]}^{: 48 }^{[7]}^{: 56 }
For a more elementary introduction of the formal definition see automata theory.
An NFA is represented formally by a 5tuple, , consisting of
Here, denotes the power set of .
Given an NFA , its recognized language is denoted by , and is defined as the set of all strings over the alphabet that are accepted by .
Loosely corresponding to the above informal explanations, there are several equivalent formal definitions of a string being accepted by :
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.
The following automaton , with a binary alphabet, determines if the input ends with a 1. Let where the transition function can be defined by this state transition table (cf. upper left picture):
Input State

0  1 

Since the set contains more than one state, is nondeterministic.
The language of can be described by the regular language given by the regular expression (01)*1
.
All possible state sequences for the input string "1011" are shown in the lower picture. The string is accepted by since one state sequence satisfies the above definition; it doesn't matter that other sequences fail to do so. The picture can be interpreted in a couple of ways:
The feasibility to read the same picture in two ways also indicates the equivalence of both above explanations.
In contrast, the string "10" is rejected by (all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state, , by reading the final 0 symbol. While can be reached after consuming the initial "1", this does not mean that the input "10" is accepted; rather, it means that an input string "1" would be accepted.
A deterministic finite automaton (DFA) can be seen as a special kind of NFA, in which for each state and symbol, 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 an 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 easiertoconstruct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to states, which sometimes makes the construction impractical for large NFAs.
Nondeterministic finite automaton with εmoves (NFAε) is a further generalization to NFA. In this kind of automaton, the transition function is additionally defined on the empty string ε. A transition without consuming an input symbol is called an εtransition and is represented in state diagrams by an arrow labeled "ε". εtransitions provide a convenient way of modeling 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.
An NFAε is represented formally by a 5tuple, , consisting of
Here, denotes the power set of and ε denotes empty string.
For a state , let denote the set of states that are reachable from by following εtransitions in the transition function , i.e., if there is a sequence of states such that
is known as the epsilon closure, (also εclosure) of .
The εclosure of a set of states of an NFA is defined as the set of states reachable from any state in following εtransitions. Formally, for , define .
Similar to NFA without εmoves, the transition function of an NFAε can be extended to strings. Informally, denotes the set of all states the automaton may have reached when starting in state and reading the string The function can be defined recursively as follows.
The automaton is said to accept a string if
that is, if reading may drive the automaton from its start state to some accepting state in ^{[4]}^{: 25 }
Let 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 where the transition relation can be defined by this state transition table:
Input State

0  1  ε 

S_{0}  {}  {}  {S_{1}, S_{3}} 
S_{1}  {S_{2}}  {S_{1}}  {} 
S_{2}  {S_{1}}  {S_{2}}  {} 
S_{3}  {S_{3}}  {S_{4}}  {} 
S_{4}  {S_{4}}  {S_{3}}  {} 
can be viewed as the union of two DFAs: one with states and the other with states . The language of can be described by the regular language given by this regular expression . We define using εmoves but 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 define an NFA where
and
One has to distinguish the transition functions of and viz. and and their extensions to strings, and respectively. By construction, has no εtransitions.
One can prove that for each string , by induction on the length of
Based on this, one can show that if, and only if, for each string
Since NFA is equivalent to DFA, NFAε is also equivalent to DFA.
The set of languages recognized by NFAs is closed under the following operations. These closure operations are used in Thompson's construction algorithm, which constructs an NFA from any regular expression. They can also be used to prove that NFAs recognize exactly the regular languages.
Since NFAs are equivalent to nondeterministic finite automaton with εmoves (NFAε), the above closures are proved using closure properties of NFAε.
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".^{[8]} 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.
There are many ways to implement a 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.