A non-deterministic machine is a 5-tuple
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.