EECS20N: Signals and Systems

Input/Output Equivalence

Consider deterministic state machine A:

and nondeterministic state machine B:

The input and alphabets for these are the same:

Inputs = { 1, absent }
Outputs = { 0, 1, absent }

These machines exhibit identical input/output behavior. Ignoring stuttering, the input can only be the sequence

1, 1, 1, 1, ...

which results in the output

0, 1, 0, 1, ...

In what sense are these machines equivalent? Obviously they are not identical, since they have different state spaces. They are bisimilar, a term we will define precisely.