EECS20N: Signals and Systems

Theorem: Input/Output Equivalence

Simulation between two machines indicates that one abstracts the other. Bisimulation indicates that they have equivalent input/output behavior. These results rest on the following theorem and corollary:

Theorem. Let B simulate A.Then

BehaviorsABehaviorsB.

Intuitively, the theorem simply states that B can match every move of A and produce the same output sequence. It also implies that if B cannot produce a particular output sequence, then neither can A. This is stated formally in the following corollary.

Corollary. Let B simulate A.Then if (x, y) ∉ BehaviorsB then (x, y) ∉ BehaviorsA.