EECS20N: Signals and Systems

Nondeterministic State Machines

In a nondeterministic state machine, a single input sequence can have several state trajectories and output sequences. Recall that in a state transition diagram, on each arc there is a guard, where


For a deterministic machine, the guards on the arcs emerging from any state are mutually exclusive (they have no common elements). Thus, given an input symbol, only one outgoing transition can possibly be enabled.

In a nondeterministic state machine, guards on arcs emerging from a state can have common elements. Thus, a given input symbol may result in more than one outgoing transition being enabled. Thus, a given input sequence has several output sequences that may result. The model does not specify which of these output sequences to use. Thus, the input does not determine the output, hence the term nondeterministic.