EECS20N: Signals and Systems

Simulation with Nondeterministic Machines

The nondeterministic machine

B = (StatesB , Inputs, Outputs, possibleUpdatesB , initialStateB )

simulates another machine with the same input and output alphabets

A = (StatesA , Inputs, Outputs, possibleUpdatesA , initialStateA )

if there is a set S StatesA× StatesB such that

  • (initialState, initialStateB ) ∈ S

and

  • If (sA , sB ) ∈ S , then
    for all x Inputs and
    for all (s'A , yA ) possibleUpdatesA (sA , x)
    there exists (s'B , yB ) possibleUpdatesB (sB , x) such that

    (s'A , s'B ) ∈ S , and
    yB = yA

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.