EECS20N: Signals and Systems

Relations

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.