EECS20N: Signals and Systems

Simulation with Deterministic Machines

A state machine

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

simulates another machine with the same input and output alphabets

A = (StatesA , Inputs, Outputs, updateA , initialStateA )
if there is a set S StatesA× StatesB such that
  • (initialState, initialStateB ) ∈ S

and

  • If (sA , sB ) ∈ S , then for all x Inputs

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

  • where

    (s'A , yA ) = updateA (sA , x)
    (s'B , yB ) = updateB (sB , x)

S is called the simulation relation between A and B.

Fact: If B simulates A with simulation relation S, and both are deterministic finite state machines, then A simulates B with simulation relation S' where

S' = { (sB , sA ) | (sA , sB ) ∈ S }

Moreover, given an input symbol, neither machine has a choice about the transition to take, since they are both deterministic. Thus, it does not matter which machines moves first in each round. Hence, if two deterministic state machines are similar, then they are bisimilar.