6.005 Elements of Software Construction | Spring 2010
Problem Set 1: State Machine Modeling
Due: 04 March 2010, 5PM

The purpose of this problem set is to (a) solidify your ability to read and interpret state machines, and (b) to increase your skill in modelling and analyzing problems using state machines.

Reading and Analyzing State Machines

Railway crossing. The state machine diagram models a railway crossing, a car and a train. Such models are used to check that designs are safe. In this case, we're concerned that a train might hit a car, and we want to make sure that the design of the crossing prevents it.



The event designations are: The machine is described as a combination of 3 small submachines operating in parallel, one describing the crossing, one describing a car, and one describing a train. Here's how it works. The crossing starts out in the UP state, and moves to the DOWN state when it detects the arrival of a train; it goes back to the up state when it detects the train's exit. The crossing allows a car to enter only in the UP state. A car waits, enters (when permitted), and then exits. A train arrives in the vicinity of the crossing, enters the crossing and then exits. Note that the machine can also be represented as a single 'composed' state machine, without parallelism. This machine would show how the train, car and crossing interact. Answer the following questions.
  1. Give a bound on the number of states of the composed machine, and say how you obtained it. It should not depend on how transitions are labeled.
  2. Draw the composed machine in full. Label each state as a tuple containing the states of the submachines that it corresponds to. How many states does this machine have? Why is it fewer than the bound you just calculated? How far, in general, can the actual number of states in a composed machine fall short of the bound?
  3. The crossing mechanism might not prevent a collision. Explain how you can tell this from looking at your composed machine. Give a trace that witnesses a collision, and explain informally what's happening.
  4. The reason a collision should not occur in practice is because of a timing assumption. Explain what this timing assumption is. Now represent the timing assumption in the state machine diagram by introducing a tick event that represents a clock ticking, and adding transitions on this event to the train and car submachines.
  5. Produce a new version of the composed machine, and say how it shows that collisions are now impossible.

Constructing State Machines

For each of the following examples, construct a state machine. The examples are only described informally; you'll need to fill in details and clarify some issues. (In fact, that's the very point of modeling: to identify gaps and potential ambiguities, and to reduce the description to something simple and clear.) In addition to the state machine itself, make sure to include (a) a designations of each event type, consisting of a carefully written one line explanation of what an occurrence of the event corresponds to in the real world, and (b) a brief commentary (in just a few sentences) explaining the key issues you resolved in your model.

Parking gate. A parking garage has a gate to limit entry to drivers who hold transponders. In the normal scenario, when a driver approaches the gate, a signal is received from the transponder and the gate opens. The gate then closes before the next car. If a driver without a transponder attempts to 'tailgate' and squeeze through while the gate is still up, a photo is taken of the license plate. To detect this, there is a pressure-sensitive strip in front of the gate that sends a control pulse whenever an axle passes over it. Model this system with a diagrammatic state machine. Hint: using parallel submachines will help.

Text completion. A textbox on a webpage accepts characters typed by the user. As the characters are typed, if they form a prefix of a word stored in a predetermined set, the set of matches is displayed. At any point, if one or more matches is shown, the user can use the arrow keys to select a match, and can terminate the selection either by pressing the arrow right key (which accepts the selection and allows more characters to be entered), by pressing the return key (which accepts the selection and submits the contents of the textbox), or by typing another character (which rejects the selection and continues the matching process). Model this system first with a diagrammatic state machine, showing the basic control flow possibilities, and then with a textual machine showing the exact state of the character buffer and suggestion list.

Hierarchical menu. When the menu is selected, it is displayed, and the user can move the cursor down and highlight either an item, or a submenu, which causes the submenu to be displayed. Moving the cursor over the submenu allows items (and further submenus) within it to be highlighted. Moving the cursor off the submenu does not cause it to be closed, unless the cursor passes over the menu that contains it. The final selection is made by clicking on the highlighted item. Model this system with a diagrammatic state machine.

Infrastructure

No code is provided for this problem set. An Eclipse project called pset1 will be created for you in your personal repository, containing a copy of this file. You should commit your solutions to the exercises as a single PDF file called pset1.pdf in the base pset1 directory.

Hints

Look over the solutions from last term's problem set, which are available here. These will give you some idea of what's involved. Remember that for this problem set, event designations are required for all the models you create.

The point of modeling is to get to grips with a problem. If your model is complicated or contains obscure elements, you probably don't understand it and should work harder at polishing it. Expect to spend half an hour or more on each of the 3 models.

In diagrammatic state machines, the idea is to show the fundamental sequences of events, and principal 'modes' of the system. You don't need to describe the complete behavior. In the menu problem, for example, you will want to distinguish whether some item is highlighted, whether a menu is open, etc, but not exactly which item is highlighted or which menu is open.

For the user interface modeling questions, you'll probably find it helpful to play with some sample widgets (for example, the menus and searchbox in your browser).

A reminder about parallelism semantics. A machine mentions an event if it appears as a label for some transition in that machine. When you have multiple machines in parallel combination, a state is combination of states, one for each submachine. An event can occur if every machine that mentions it can take a transition on that event. So in each step, one or more submachines takes a step.

In the railway crossing example, note that the CAR machine never mentions any of the train events. So an exitT event for example, can happen without the participation of the CAR machine. Don't view this as a self-transition for the CAR machine; it simply doesn't see the event. In contrast, the enterC event is shared with the CROSSING machine. This means that an enterC can't happen unless both the CROSSING and CAR machines perform it together. So if the CROSSING is in the DOWN state and the CAR is in the WAITING state, the CAR cannot perform an enterC because the CROSSING does not permit it. Once the CROSSING has taken a transition to UP on exitT, however (which requires joint participation of the CROSSING and TRAIN machines, but not the CAR machine), the enterC may then occur.

The power of state machines comes from their simplicity. Don't confuse state machine diagrams with control flow diagrams, and resist the urge to extend the notation in an ad hoc way. Remember to make sure that: