The Art of the State:
Modelling Design with FSMs

An FSM is a virtual machine characterised by a set of internal states, a set of external events, and a set of transitions between the states. You might also hear FSMs referred to as Finite State Automata, Deterministic Finite Automata, or simply State Machines. FSMs can be used to model an entire application, a small part of it, or both, and they are extremely common in the design of real-time systems, compilers, and communications protocols. FSMs are ideal tools for representing event-driven programs such as GUIs.

States are labels assigned to particular sets of circumstances within the application. Although FSMs are often used to model the GUI part of applications, states are not forms, and events are not necessarily Visual Basic events. We generate a set of predefined events from real-world stimuli and apply them as inputs to the FSM to drive it through transitions into different states. Transitions can have arbitrary lists of actions associated with them, and these actions are executed as we drive the FSM from state to state by repeatedly applying events. An FSM is deterministic because each combination of state and event unambiguously defines the next state to move into.

We can represent an FSM as a state transition diagram or as a pair of tables, one table defining the next state to move into when a particular state/event combination is detected and the other table defining a list of actions to be performed along the way. Figure 2 shows an FSM that defines a program to strip C comments out of a text stream (comments in C are delimited by /* and */).

The circles represent states, and the arrows represent transitions between states. Each transition is labelled with the event that stimulates it and the list of associated actions. One state is designated the start state, which is the initial state when the FSM starts to operate. Here is the FSM in tabular form:

State Table
                   State

Event	Outside	Starting	Inside	Ending
/	Starting	Starting	Inside	Outside
*	Outside	Inside	Ending	Ending
Any other char	Outside	Outside	Inside	Inside

Action Table
                   State

Event	Outside	Starting	Inside	Ending
/	N/A	Print "/"
*	Print char
Any other char	Print char	Print "/" Print char

These tables provide the basis for implementing an FSM as a program. An FSM program has the following elements:

• A static variable to track the current state and a set of constants to represent all available states
• A table or equivalent program network to look up a state/event pair and decide which state to move into
• A set of constants to represent FSM events
• A driver loop that captures real-world events and decodes the state/event pair

Figure 3 shows a GUI fragment modelled on a real application. This application provides a summary and two different detailed views of a database. The forms are modeless, so the user can edit any form on the screen, potentially invalidating data on either of the other forms. Although the maximum possible number of states is seven, the design of this application permits access to only four combinations of forms: A, A + B, A + C, and A + B + C. The only events we'll consider are the button clicks; there are 11 buttons, so 11 is the number of events that must be accounted for in every state.

The application has been designed so that only form A's OK or Apply button commits data to the database. Each form has a buffer in which it holds edits to its own subset of the data, and the contents of these buffers are shuffled around as the OK, Apply, and Cancel buttons are manipulated on forms B and C. Figure 4 shows the state transitions for this GUI, and Figure 5 is a close-up view of two states, showing the actions the application will take on each transition.

Close examination of Figures 4 and 5 reveals some omissions. There are 11 events, but not all states have 11 arrows leaving them. This is partly because not all events can occur in all states. For example, it isn't possible to click form C's Apply button in state 1. But some events, such as the Details button events in states 2 and 3, are omitted because there just isn't enough space for them. Leaving out events like this undermines a basic reason for using an FSM, which is to verify that we've considered all state/event combinations. This is where the tabular form is a much better representation – it's easier to draw, and it clearly shows all state/event combinations. The two notations complement each other: in practice the state diagram is a useful sketch that conveys the feel of the GUI, while the tables provide a basis for implementation.

The End of the Elegance

The finite state machine (FSM) notation is simple and elegant, but we run into problems when we try to apply it to real programs. One class of problem, the conditional state transition, is exemplified by the need for validation when we're unloading forms. For example, if we consider form B's OK Click event, we can see that the FSM changes state and does the associated actions unconditionally. If we want to do a form-level validation before committing changes, we'll have a problem. In practice, the solution depends on how far we're prepared to go in carrying the FSM through into the implementation of our program. For smaller applications, it's wise to stop at the design stage and just use the state diagram and tables for guidance when writing the program. For more complex programs, we can carry the FSM right through to the implementation, as we'll see below.

For a pure FSM implementation, we can get around the validation issue by introducing extra states into the machine. Figure 6 shows a new state between states 2 and 1 for form B's OK event. The only difference is that this state is transient because the FSM immediately flips out of it into state 1 or state 2. This happens because we queue an event for the new state before we even get there. Validation states are also required for confirmation, such as when a user tries to abandon an edited form without saving changes.

Figure 6: Introducing transient states to avoid conditional transitions

Next...