EECS20N: Signals and Systems

Simulation and Abstraction

Consider a nondeterministic state machine C:

Compare with the deterministic state machine A:

Considering again the same game, C can match anything A does, but now the relationship is not symmetric. C can produce the output sequence

0, 0, 1, 1, ...

for example, while A can only produce (ignoring stuttering):

0, 1, 0, 1, ...

Thus, C simulates A, but A does not simulate C. C is said to be an abstraction of A because it has all of the possible behaviors of A, but fewer constraints (so it can have behaviors that A cannot have). In this sense (fewer constraints), C is a less detailed model.

The simulation relation for this case is very simple:

{ (0and2, 0to3), (1and3, 0to3) }.