EECS20N: Signals and Systems


A deterministic machine determines an input-output function

H: InputSignals OutputSignals

A non-deterministic machine determines an input-output relation

Behaviors = { (x, y) | y is a possible output sequence corresponding to input x }

The relation, like the graph of the function, satisfies

Behaviors InputSignals × OutputSignals

but unlike the graph of the function, for any given x InputSignals, there may be more than one y OutputSignals. Thus, Behaviors is not the graph of a function for nondeterministic machines.