Nondeterministic finite automaton

In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
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 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.
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. 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, 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.
There are several informal explanations around, which are equivalent.
Formal definition.
For a more elementary introduction of the formal definition see automata theory.
Automaton.
An "NFA" is represented formally by a 5-tuple,
formula_1, consisting of
Here, formula_9 denotes the power set of formula_2.
Recognized language.
Given an NFA formula_11, its recognized language is denoted by formula_12, and is defined as set of all strings over the alphabet formula_3 that are accepted by formula_14.
Loosely corresponding to the above informal explanations, there are several equivalent formal definitions of a string formula_15 being accepted by formula_14:
Initial state.
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 a NFA with multiple initial states to a NFA with single initial state, which provides a convenient notation.
Example.
The following automaton formula_14, with a binary alphabet, determines if the input ends with a 1.
Let formula_52 where
the transition function formula_4 can be defined by this state transition table (cf. upper left picture):
Since the set formula_54 contains more than one state, formula_14 is nondeterministic.
The language of formula_14 can be described by the regular language given by the regular expression codice_1.
All possible state sequences for the input string "1011" are shown in the lower picture.
The string is accepted by formula_14 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 formula_14 (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, formula_69, by reading the final 0 symbol. While formula_69 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.
Equivalence to DFA.
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 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 formula_71 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, formula_1, consisting of
Here, formula_9 denotes the power set of formula_2 and ε denotes empty string.
ε-closure of a state or set of states.
For a state formula_81, let formula_82 denote the set of states that are reachable from formula_69 by following ε-transitions in the transition function formula_4, i.e.,
formula_85 if there is a sequence of states formula_86 such that
formula_82 is known as the ε-closure of formula_69.
ε-closure is also defined for a set of states. The ε-closure of a set of states, formula_93, of an NFA is defined as the set of states reachable from any state in formula_93 following ε-transitions. Formally, for formula_95, define formula_96.
Accepting states.
Let formula_15 be a string over the alphabet formula_3. The automaton formula_14 "accepts" the string formula_17 if a sequence of states,
formula_18, exists in formula_2 with the following conditions:
In words, the first condition says that the machine starts 
at the state that is reachable from the start state formula_24 via ε-transitions. The second condition says that after reading formula_109,
the machine takes a transition of formula_4 from formula_111 to formula_112,
and then takes any number of ε-transitions according to formula_4 to move from formula_112 to formula_115. 
The last condition says that the machine accepts formula_17 if the last input of formula_17 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 formula_14 accepts is the language "recognized" by formula_14 and this language is denoted by formula_12.
Example.
Let formula_14 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 formula_122 where
the transition relation formula_4 can be defined by this state transition table:
formula_14 can be viewed as the union of two DFAs: one with states formula_125 and the other with states formula_126. 
The language of formula_14 can be described by the regular language given by this regular expression formula_128.
We define formula_14 using ε-moves but formula_14 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 formula_131 be a NFA-ε. 
The NFA formula_132 is equivalent to formula_133, where for each formula_134 and formula_81, formula_136.
Thus NFA-ε is equivalent to NFA. Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA.
Closure properties.
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.
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 can 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:
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.