EECS20N: Signals and Systems

Modeling Nondeterministic State Machines

A non-deterministic machine is a 5-tuple

N = > (States, Inputs, Outputs, possibleUpdates, initialState)

where everything is the same as a deterministic state machine except that instead of

update: States × Inputs → States × Outputs

we have

possibleUpdates: States × Inputs → P(States × Outputs)

where P(States × Outputs) is the power set of States × Outputs.

The power set of a set is the set of all subsets. That is,

P(States × Outputs) = { A | A ⊂ States × Outputs }

Thus, for a given state s ∈ States and input symbol x ∈ Inputs, possibleUpdates(s, x) gives all possible transitions enabled by x together with the corresponding output from each such transition.