CMU 15-671Models of Software SystemsFall 1995
Relating State Machines: Equivalence
Garlan & Wing Handout 8 9 October 1995
So far we have seen what a state machine is and how it can be used to model concepts like system behavior, input actions (or events) with arguments, output actions (or events) with results, and nondeterminism. We have even hinted at how a state machine would be an appropriate model of an abstract data type, and hence one of the bases for object-oriented programming.
We have also seen that given a state machine we can reason about some of its properties, most importantly, invariants.
In this and the next handout we consider the following question: ``Given two state machines, how are they related?'' This handout discusses the relationship of equivalence between two state machines. The next handout discusses the problem of whether one machine satisfies (in some sense) another. We won't be spending any time in this course defining different notions of equivalence or showing two state machines equivalent. Hence this handout is short and to be read for edification.