EECS20N: Signals and Systems

• Home
•  Up to Topics
•  Previous
•  Next

Week 4

• Nondeterminism
• Example
• Model
• Possible updates
• Relations
• Abstraction
• Equivalence
• Simulation
• Deterministic
• Abstraction
• Nondeterministic
• Behaviors
• Theorem
• Not theorem
• Uses
• Bisimulation
• Examples

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

A = (States_A , Inputs, Outputs, update_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

  (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.