Glossary Table of 
Contents Index 
(Note: the black diamond route is the challenging approach to learning about the material, with the exception that multiple black diamonds represent even more challenging routes. Usually what this means is that a rather terse, abstract, and mathematical approach to the material is given with only a few examples and illustrations. An example is given below, albeit one that is not completely fleshed out).
Nondeterminism plays a key role in the theory of computing. A nondeterministic finite state automaton is one in which the current state of the machine and the current input do not uniquely determine the next state. This just means that a number of subsequent states (zero or more) are possible next states of the automaton at every step of a computation.
Of course, nondeterminism is not realistic, because in real life, computers must be deterministic. Still, we can simulate nondeterminism with deterministic programs. Furthermore, as a mathematical tool for understanding computability, nondeterminism is invaluable.
As with deterministic finite state automata, a nondeterministic finite state automaton has five components.
a set of states
a finite input alphabet from which input strings can be constructed
a transition function that describes how the automaton changes states as it processes an input string
a single designated starting state
a set of accepting states
The only difference lies in the transition function, which can now target subsets of the states of the automaton rather than a single next state for each state, input pair. Formally, a nondeterministic finite state automaton can be defined as follows:
(Note: The following definition uses special symbols from the Microsoft Symbol font. The symbols may be unreadable unless your browser is running on PC with a Microsoft operating system. Mathematical notation is one of the challenges yet to be met in the construction of Snapshots. Mathematics could be inserted by way of .gif images (e.g., via the latex2html utility). This is an unsatisfactory solution, however. The best solution is to use MathML. Right now software for including and displaying MathML is in short supply. All reports indicate, however, that all of the popular browsers will eventually be able to render MathML directly. For the time being, we plan to proceed by using a commercial MathML editor.)
Definition
A nondeterministic finite state automaton (nfsa) is a five-tuple, M = (Q, S, d, q0, F), where Q is a finite set of states, S is a finite input alphabet, d is a transition function, d: Q ´ S ® 2Q, q0 Î Q is the starting state, and F--a subset of Q--is a set of accepting states.
Notice how the definition of the transition function differs from that for a deterministic finite state automaton.
As a diagram, a nondeterministic finite state automaton looks no different than a deterministic finite state automaton. It is simply a directed, labeled graph. The only difference is that there can be more than one arrow leading from a state with the same label (the nondeterminism).
There are many ways to visualize an nfa. One is to think of the nfa as having each possible state it may be in colored a particular way. As the next input symbol is processed, the currently colored states are uncolored, and the next states are colored according to how each currently colored state responds to the input. Following is an example of an nfa that determines whether an arbitrary binary string ends in with 101 or 110.
Example 1.
Glossary Table of Contents Index