CMU 15-671Models of Software SystemsFall 1995
Sequences, Induction; State Machines
Garlan & Wing Homework 4 Due: 20 September 1995

Problem 1.

Chapter 7 of SEM: 7.1, 7.2, 7.3

Problem 2.

Chapter 8 of SEM: 8.2, 8.3, 8.7, 8.8

Problem 3.

A certain simple answering machine (not unlike the one on my desk) has two buttons (``play'' and ``save'') and (of course) can receive messages. If someone plays the messages and doesn't save them, they are erased/overwritten when the next incoming message is received. The answering machine only holds a specified number of messages; when it reaches full capacity, it refuses to accept new messages. The answering machine can be modeled by the state machine AnsMachine whose state transition diagram is below.

1. Give a 4-tuple description for this state machine.
2. Give three execution fragments of AnsMachine, at least one of which is not an execution.
3. Give both a finite and an infinite execution of AnsMachine.
4. For each of the following, indicate whether or not it is an event-based trace of AnsMachine.
   1. play save msg msg play
   2. msg msg msg play save msg msg msg
   3. msg play save msg msg play msg msg msg
5. Give two examples of state-based traces of AnsMachine.
6. Give two sequences of states which are not state-based traces of AnsMachine.
7. What are the reachable states of this machine?
8. Is AnsMachine's event-based behavior finite or infinite?
9. Can a state machine with an infinite trace have an infinite behavior? Give an example or explain why not.

• About this document ...