[Overview] [Previous] [Next]

Nondeterministic Finite Acceptors

A finite-state automaton can be nondeterministic in either or both of two ways:

nfa with multiple arcs A state may have two or more arcs emanating from it labeled with the same symbol. When the symbol occurs in the input, either arc may be followed.
nfa with empty transition A state may have one or more arcs emanating from it labeled with (the empty string) . These arcs may optionally be followed without looking at the input or consuming an input symbol.

Due to nondeterminism, the same string may cause an nfa to end up in one of several different states, some of which may be final while others are not. The string is accepted if any possible ending state is a final state.