EECS20N: Signals and Systems

Not Theorem!

Note that the theorem does not say that if


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