• 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

Not Theorem!

Note that the theorem does not say that if

Behaviors_A ⊂ Behaviors_B

then B simulates A. In fact, that assertion is false! Consider the following two machines:

These two machines have exactly the same behaviors. Thus, it is certainly true that Behaviors_A ⊂ Behaviors_B (recall that ⊂ means "subset or equal" in our notation). However, (b) does not simulate (a). To see this, note that there is no state in (b) that you can pair with b and still be able to match any move that machine (a) takes.