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.

[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).

Besides the DFAs, other known special cases of NFAs are unambiguous finite automata (UFA) and self-verifying finite automata (SVFA).

There are at least two equivalent ways to describe the behavior of an NFA.

In each step, the automaton nondeterministically "chooses" one of the applicable transitions.

[4][5]: 319 [6] In the second way, the NFA consumes a string of input symbols, one by one.

If no transition is applicable, the current copy is in a dead end, and it "dies".

[4][7][6] For a more elementary introduction of the formal definition, see automata theory.

Loosely corresponding to the above informal explanations, there are several equivalent formal definitions of a string

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 M, with a binary alphabet, determines if the input ends with a 1.

All possible state sequences for the input string "1011" are shown in the lower picture.

In contrast, the string "10" is rejected by M (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, q, by reading the final 0 symbol.

Conversely, for each NFA, there is a DFA such that it recognizes the same formal language.

It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs.

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 "ε".

The set of languages recognized by NFAs is 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 machine starts in the specified initial state and reads in a string of symbols from its alphabet.

Until these subsequent events occur it is not possible to determine which state the machine is in".

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.

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.

For example, it is much easier to prove closure properties of regular languages using NFAs than DFAs.