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.