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.

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.

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.