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:
“Any language is necessarily a finite system applied with different degrees of creativity to an infinite variety of situations, and most of the words and phrases we use are “prefabricated” in the sense that we don’t coin new ones every time we speak.”
—David Lodge (b. 1935)