Nondeterministic finite automaton

From Wiki @ Karl Jones dot com
Jump to: navigation, search

In automata theory, a nondeterministic finite automaton (NFA), or nondeterministic finite state machine, is a finite-state machine which does not need to obey certain restrictions which apply to deterministic finite automata (DFA).

Description

The restrictions which an NFA does not need to obey:

  • Each of its transitions is uniquely determined by its source state and input symbol
  • Reading an input symbol is required for each state transition

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. Sometimes the term NFA is used in a narrower sense, meaning an automaton that properly violates an above restriction, i.e. that is not a DFA.

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.

See also

External links