Simulation with Nondeterministic Machines

The nondeterministic machine

B = (States_B , Inputs, Outputs, possibleUpdates_B , initialState_B )

simulates another machine with the same input and output alphabets

A = (States_A , Inputs, Outputs, possibleUpdates_A , initialState_A )

if there is a set S Ì States_A´ States_B such that

• (initialState_A  , initialState_B ) Î S

and

• If (s_A , s_B ) Î S , then
  for all x Î Inputs and
  for all (s'_A , y_A ) Î possibleUpdates_A (s_A , x)
  there exists (s'_B , y_B ) Î possibleUpdates_B (s_B , x) such that

  (s'_A , s'_B ) Î S , and
  y_B = y_A

S is called the simulation relation between A and B.

Unlike the simulation relation for deterministic machines, this says that B can match A, not that it must match A. Thus, this relation is not symmetric. It is not necessarily true that A simulates B.

Note that a deterministic machine is a special case of nondeterministic machines where possibleUpdates always returns a set with exactly one element. Thus, the above definition applies to all state machines, deterministic or not.