Editing Nondeterministic finite automaton (section)

{{Short description|Type of finite-state machine in automata theory}}
[[File:Relatively small NFA.svg|100px|thumb|NFA for [[regular expression|(0<nowiki>|</nowiki>1)<sup>*</sup>&nbsp;1&nbsp;(0<nowiki>|</nowiki>1)<sup>3</sup>]].<br />A [[deterministic finite automaton|DFA]] for that [[formal language|language]] has at least 16 states.]]
In [[automata theory]], a [[finite-state machine]] is called a [[deterministic finite automaton]] (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and 
* reading an input symbol is required for each state transition.
A '''nondeterministic finite automaton''' ('''NFA'''), or '''nondeterministic finite-state machine''', does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term '''NFA''' is used in a narrower sense, referring to an NFA that is ''not'' a DFA, but not in this article.

Using the [[subset construction algorithm]], each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same [[formal language]].<ref>{{cite book |title=Introduction to Languages and the Theory of Computation |last1=Martin |first1=John |year=2010 |page=108 |publisher=McGraw Hill |isbn= 978-0071289429}}</ref>
Like DFAs, NFAs only recognize [[regular language]]s.
 
NFAs were introduced in 1959 by [[Michael O. Rabin]] and [[Dana Scott]],{{sfn|Rabin|Scott|1959}}  who also showed their equivalence to DFAs. NFAs are used in the implementation of [[regular expression]]s: [[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).

NFAs have been generalized in multiple ways, e.g., [[#NFA with ε-moves|nondeterministic finite automata with ε-moves]], [[finite-state transducer]]s, [[pushdown automaton|pushdown automata]], [[Alternating finite automaton|alternating automata]], [[ω-automaton|ω-automata]], and [[probabilistic automaton|probabilistic automata]].
Besides the DFAs, other known special cases of NFAs
are [[unambiguous finite automaton|unambiguous finite automata]] (UFA)
and [[self-verifying finite automaton|self-verifying finite automata]] (SVFA).