Nondeterministic finite automaton
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
- Deterministic finite automaton
- Finite-state machine
- Pushdown automaton
- Regular expression
- Turing Machine
External links
- Nondeterministic finite automaton @ Wikipedia
