Finite State Machines

In some cases it's convenient to regard the system or a discrete subset of the system as a "hypothetical machine that can be in only one of a given number of 'states' at any specific time" [Davis 1993]. In response to an input, such as data entry from the user or an input from an external device, the machine changes its state and then generates an output or carries out an action. Both the output and the next state can be determined solely on the basis of understanding the current state and the event that caused the transition. In that way, a system's behavior can be said to be deterministic; we can mathematically determine every possible state and, therefore, the outputs of the system, based on any set of inputs provided.

Hardware designers have used finite state machines (FSMs) for decades, and a large body of literature describes the creation and analysis of such machines. Indeed, the mathematical nature of the FSM notation lends itself to formal and rigorous analysis, so that the problems of consistency, completeness, and ambiguity described earlier in Team Skill 5 can be largely mitigated using this technique.

A popular notation for FSMs is the state transition diagram (Figure 24-2). In this notation, the boxes represent the state the device is in, and the arrows represent actions that transition the device to alternative states. Figure 24-2 illustrates state transitions for the light box described in Chapter 23. In that example, the natural language expression "the other light shall flash every 1 second" was ambiguous. The state transition diagram in Figure 24-2 is not ambiguous since it illustrates that duty cycle B was indeed the right choice. If a bulb burns out, the device alternates between attempting to light the even light and attempting to light the odd light, each for a period of one second.

Figure 24-2. Example of a state transition diagram

Here's an interesting exercise to try. Consider using the FSM technique to restate the HOLIS Control Light use case. You may immediately notice that the Dim alternative flow in the use case lends itself nicely to the FSM style of representation.

An even more precise form of representing an FSM is the state transition matrix, which is represented as a table that shows every possible state the device can be in, the output of the system for each state, and the effect of every possible stimulus or event on every possible state. This ensures a higher degree of specificity because every state and the effect of every possible event must be represented in the table. For example, Table 24-1 defines the behavior of our light box in the form of a state transition matrix.

With this technique, we can resolve additional ambiguities that may have been present in our attempt to understand the behavior of the device.

• What happens if the user presses the On switch and the device is already on? Answer: Nothing.

• What happens if both bulbs are burned out? Answer: The device powers itself off.

Table 24-1. Example of a State Transition Matrix for an On/Off Counting Device

	Event
State	On Press	Off Press	Count Press	Bulb Burns Out	Every Second	Output
Off	Even lit	”	”	”	”	Both off
Even lit	”	Off	Odd lit	LO/Even lit	”	Even lit
Odd lit	”	Off	Even lit	LO/Odd lit	”	Odd lit
Light out/Even lit	”	Off	”	Off	LO/Odd lit	Even lit
Light out/Odd lit	”	Off	”	Off	LO/Even lit	Odd lit

FSMs are very popular for certain categories of systems programming applications, such as message-switching systems, operating systems, and process control systems. FSMs also provide an elegant way to describe the interaction between an external human user and a system (consider, for example, the interaction between a bank customer and an automated teller machine when the customer wants to withdraw money). However, FSMs can become unwieldy, particularly if we need to represent the system's behavior as a function of several inputs. In such cases, the required system behavior is typically a function of all current conditions and stimuli rather than the current stimulus or a history of stimuli.