Nondeterministic finite automata (NFA) have transition functions which
may assign several or no states to a given state and an input symbol.
They accept a word if there is any possible transition from the
one of initial states to one of the final states. It is important to note that
although NFAs have a non-determistic transition function, it can
always be determined whether or not a word belongs to its language
(). Indeed we shall see that every NFA can be translated
into an DFA which accepts the same language.
Here is an example of an NFA which accepts all words over
s.t. the symbol before the last is
.
A nondeterministic finite automaton (NFA)
is given by:
Hence, the only difference to DFAs are to have start staes instead of a single one and the type of the transition function. As an example we have that
Note that we diverge he slightly from the definition in the book,
which uses a single initial state instead of a set of initial
states. Doing so means that we can avoid introducing -NFAs
(see section 2.5 of the book).