A *nondeterministic finite acceptor* or *nfa* is defined by the
quintuple

- Q is a finite set of
*states,* - is a finite set of
symbols, the
*input alphabet,* - : Q
(
{ }
) 2
is a
*transition function,* - q0 Q
is the
*initial state,* - F Q is
a set of
*final states.*

- Transitions on are allowed in addition to transitions on elements of , and
- The range of is 2 rather than Q. This means that the values of are not elements of Q, but rather are sets of elements of Q.

Copyright © 1996 by David Matuszek

Last modified Jan 29, 1996