In the automata theory, a nondeterministic finite automaton (NFA) or nondeterministic finite state machine is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined. Although the DFA and NFA have distinct definitions, a NFA can be translated to equivalent DFA using powerset construction, i.e., the constructed DFA and the NFA recognize the same formal language. Both types of automata recognize only regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs.
NFAs are sometimes studied by the name subshifts of finite type. NFAs have been generalized multiple ways, e.g., nondeterministic finite automaton with ε-moves, pushdown automaton, ω-automaton, probabilistic automata.
Read more about Nondeterministic Finite Automaton: Informal Introduction, Formal Definition, Example, Variations of NFA, Equivalence To DFA, Closure Properties, Properties, Implementation, Application of NFA
Famous quotes containing the word finite:
“For it is only the finite that has wrought and suffered; the infinite lies stretched in smiling repose.”
—Ralph Waldo Emerson (1803–1882)