# Simulation with Deterministic Machines

A state machine

*B *= (*States _{B }*,

*Inputs*,

*Outputs*,

*update*,

_{B}*initialState*)

_{B }**simulates** another machine with the same input and output alphabets

if there is a setA= (States,_{A }Inputs,Outputs,update,_{A}_{}initialState)_{A }

*S*⊂

*States*×

_{A}*States*such that

_{B}- (
*initialState*,_{A }*initialState*) ∈_{B }*S*

and

- If (
*s*,_{A }*s*) ∈_{B }*S*, then for all*x*∈*Inputs*(

*s'*,_{A }*s'*) ∈_{B }*S*, and

*y*=_{B}*y*_{A}

where

(

s',_{A}y) =_{A}update(_{A}s,_{A}x)

(s',_{B}y) =_{B}update(_{B}s,_{B }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'* = { (*s _{B }*,

*s*) | (

_{A}*s*,

_{A }*s*) ∈

_{B }*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.