Karl Jones: Created page with "In automata theory, a '''nondeterministic finite automaton''' (NFA), or '''nondeterministic finite state machine''', is a finite-state machine which does not need to obey..."

2016-08-26T22:20:29Z

Created page with "In automata theory, a '''nondeterministic finite automaton''' (NFA), or '''nondeterministic finite state machine''', is a finite-state machine which does not need to obey..."

New page

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 automaton|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 expression|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 ==

* [https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton Nondeterministic finite automaton] @ Wikipedia

[[Category:Computer science]]
[[Category:Computing]]

Nondeterministic finite automaton - Revision history

Karl Jones: Created page with "In automata theory, a '''nondeterministic finite automaton''' (NFA), or '''nondeterministic finite state machine''', is a finite-state machine which does not need to obey..."