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