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

Abstraction

One key use of nondeterministic state machines is to abstract complicated state machines with simpler ones. Consider the parking meter example. That example has enough states that drawing a state transition diagram is awkward. Here is a sketch of such a diagram:

This diagram is missing many of the states, and even then is fairly confusing. Consider the following nondeterministic state machine with the same input and output alphabets as the parking meter:

This machine is non-deterministic. It hides details of the top machine (it is an abstraction of the top machine). The bottom machine can produce output sequences that the top one cannot, such as

expired, safe, safe, expired, safe, safe, expired, … Thus, the two machines are not equivalent. We will relate the two machines using the notion of simulation.