This article will help you understand how to design a state machine from a general description of a problem. A classic traffic-light-controller provides an elementary test case.
The Basic Principle
State machines are often used to solve certain kinds of control-oriented problems where designers can picture the control flow moving through a set of distinct states. There are a number of definitions and practical descriptions of a state machine. At a theoretical level think of it as a kind of automaton that changes its state in response to a particular stimulus. Matching a specific regular expression, for example, can be considered such an automaton that reacts to the input string by moving through a set of states. If the state machine reaches a goal state, the input string must have matched the regular expression.
In control software, developers commonly base the state-machine computational model on finiteness and determinism, which basically means the state machine has a finite number of states or state combinations, and the state machine can exist in only one state at a time. Later you will see that the one-state-at-a-time rule can be relaxed, but the important point is that current state is a deterministic property.
If you are new to state machines implemented in software, the most important concepts are highlighted below and shown in Figures 1-1, 1-2 and 1-3.
1. States: A state provides a shorthand description of the current situation in the system. As a simple example, consider a TV set that has three top-level operating modes: on, off or standby.
2. Events: An input message to the state machine comprises an event. The event might cause the state machine to change state. Pressing the On button on a TV set in its standby mode, for example, switches the TV into the On state.
3. Transitions: A transition is a directed path from one state to another state. State-machine diagrams typically label a transition with an event name. The label indicates the transition will take place if the specified event occurs when the state machine is in the state at the beginning of the labeled transition, that is the origin of the arrow as shown in Figure 1. In that case, the state machine changes state to the goal state of the transition at the end of the arrow. To increase the expressive power of the state-machine notation, a transition might have guard conditions that must be fulfilled for the transition to take place.
4. Actions: An action represents an activity the state machine will perform at a given time. Typically an action carries out a task such as reading from or writing to an I/O device. You can specify actions associated with transitions, or you can specify actions as a state machine enters or exits specific states.
These four concepts are fundamental to the formalized approach to state-machine design that exists as a subset of the Unified Modeling Language (UML).
Beyond the Basics
A classic textbook state-oriented problem lets us implement a basic state machine:
A little-used farm road intersects a busy highway. Detectors along the farm road raise signal C as long as a vehicle waits to cross the highway. The traffic-light controller should operate as follows: As long as it detects "no vehicle" on the farm road, the lights should remain green for highway traffic. If the controller detects a vehicle on the farm road, the highway lights should change green to yellow and then to red. Then the farm-road lights turn green. The farm-road lights stay green only for as long as the controller detects a vehicle waiting to cross the highway and never stays green on the farm road for longer than a set interval, so that traffic to flow smoothly along the busy highway. When these conditions are met, the farm-road lights change from green to yellow to red, and the highway lights change to green. Even if vehicles are waiting on the farm road to cross the highway, the highway lights should remain green for a set interval.
This exercise takes a hardware perspective, but with a little "artistic" freedom you can adapt it to suit software development. Note that this example uses the convention that yellow light is always shown by itself (some geographic areas use different conventions). This condition makes it easier to keep track of the traffic-light color combinations.
Think of the simple approach to designing state machines in the following steps:
1. Identify events and actions
2. Identify states
3. Group by hierarchy
4. Group by concurrency
5. Add transitions
6. Add synchronizations
This is not a prescriptive recipe, but rather an approach that will generally help when you structure a solution, regardless of the tools and implementation methods you choose.
Drilling Down
Start by examining the problem description and looking for possible events and actions. What constitutes an event in a state-machine context? In short, an event is a kind of trigger that could make the state machine change state and perform some action. In the traffic-light example we can find a number of potential events:
* The arrival of traffic on the farm road has meaning for the traffic-light controller.
* There are two timing intervals involved in the description:
1. The minimum time the highway light stays green. This can also be used as the fixed time for the farm road light to stay green so several vehicles can cross the highway.
2. The delay time when switching to and from yellow light on both roads.
The delay intervals are not events in themselves, but you can view the end of an interval as an event. In effect this leaves us with two events, the long-interval event for the green period on both roads, and the short uniform delay when transitioning through the light sequence from red to green and from green to red.
This leaves us with three events which we can call FarmRoadTrafficEvent, LongTimerEvent and ShortTimerEvent.
So, what makes up an action in the traffic-light problem? Changing the color of the traffic lights is a typical action. The only question is whether it requires one or two actions to change the light on both roads. The answer is that this is really a convenience issue. We can regard it as two different actions, where each action takes care of one road, or we can see it as one action. I choose to view it as two distinct actions.
I call the actions SetFarmRoadLight() and SetHighwayLight(), and each action takes a color parameter that indicates the desired traffic light color to turn on. The idea here is that the events we have chosen will trigger changes - under certain situations - in the colors the traffic light displays.
Further, we need some way to keep track of the timing intervals, so we introduce a special action called a timer action that starts a counting timer for a specified interval and keeps track of an event the timer will trigger when the timed period ends. I have called this timer action TimerAction().
To get a grip on the control logic for the traffic-light system we must look into possible states and transitions between them. The first solution will use the observations that:
• At any time the traffic lights will show one of the following color combinations, with one light lit for the farm road and the other lit for the highway: {GREEN, RED}, {YELLOW, RED}, {RED, RED}, {RED, YELLOW}, {RED, GREEN}, {RED, YELLOW}. (The first color in each pair is the highway light.) To prevent accidents, no other light combinations should exist.
• There is a fixed sequence in which the above color combinations will appear: {GREEN, RED}, {YELLOW, RED}, {RED, RED}, {RED, YELLOW}, {RED, GREEN}, {RED, YELLOW}, {RED, RED}, {YELLOW, RED} and then back to the first combination to loop through the sequence again.
You can view each of the eight light combinations in the above sequence as a possible state, because it describes the state of the controller at a given time. The different timing intervals for each color changeover would then trigger transitions from state to state. If we assume the sequence would start with the green light turned on for the highway traffic, then the complete sequence gets its start with a FarmRoadTrafficEvent.
You might have noticed that the above sequence of color combinations includes several duplicates, for example {RED, RED} and {YELLOW, RED}. Should we treat the duplicates as one state or two? To keep things simple I have treated all eight light combinations as separate states. Now we have the basic information; a set of events, some actions, and a set of candidate states.
Figure 2 shows the traffic-light design in Unified Modeling Language (UML) notation. The proposed states appear in a circular fashion with transitions named by the corresponding events. The states also have entry actions to change the color of the lights for each road. As we can see, only the start state needs to set both lights to ensure a proper start to the sequence. For all the other states, only one of the lights needs to change from the previous state. This is the reason for using two different action functions. The start state is indicated by the transition from the initial state, denoted by the small circle in the upper left corner of Figure 2.
The semantics of UML use the initial state and the transition from it to point to the desired start state, which means that we can express system initialization directly in the diagram. The transition is event-less and implicit at start-up of the controller.
From a state-machine perspective, this design looks almost complete but it lacks the handling of the minimum green interval on the highway. We can solve this in a number of ways, but the following solution seems easy enough.
• Add a level of hierarchy to the model by creating a "small" state machine within the GreenH_RedF state, as shown in Figure 3. This state machine comprises two states plus the initial pseudo state. Whenever the surrounding state is entered, the NewGreen state will also be activated. (Note that Figure 3 shows only a portion of the complete state machine shown previously in Figure 2.)
• When the long timer interval--initiated by entering GreenH_RedF - expires we let the small state machine change state to FarmRoadEventOK. Now we know that the minimum green interval has passed for illumination of the green light for the hightwy, and the traffic light should now ‘go green' on the farm road if it has traffic waiting on it for a green light.
• The last piece needed to keep the minimum green interval on the highway is a ‘guard' on the transition out of the GreenH_RedF state. This transition should only be triggered if the FarmRoadEventOK state is activated. This can be expressed by a so-called positive state condition or positive synchronization on the transition.
This solution is not perfect, because it does not address the fact that traffic which arrives on the farm road during the highway minimum green interval is stuck until another car arrives after the expiration of the interval. To solve this, we need to record any FarmRoadTrafficEvent that occurs during the green interval, so we can take appropriate action when the interval expires. I won't discuss a complete solution to that problem here, but if you try to create a design that handles this situation, the following points provide some hints:
• Introduce a state machine internal-flag variable that is initialized to zero at each entry to the highway green state
• Introduce an 'internal reaction' on the highway green state that sets the flag if a FarmRoadTrafficEvent is received, maybe with NewGreen as a guard state
• An 'entry reaction' in the FarmRoadEventOK state that sends a signal if the flag is set when entering the state. (A signal is a special event that can be sent by the state machine itself.)
• A transition to Yellow that triggers on the signal and starts the short interval timer.
There are other ways to deal with this problem, but they require a deeper understanding of UML syntax, and that topic goes beyond the scope of this introduction.
Software state machines differ from their hardware counterparts because a software state machine must detect and react to events in a hardware environment. This means developers base the computational model of software state machines on a detect-event-and-react-to-event cycle that comprises discrete steps. On the other hand, a hardware state machine can detect and react ‘simultaneously' to a changed signal on a pin. A gate can combine several logic signals, for example, to produce a single event when the input signals meet a preset condition. In a software environment you must let interrupt handlers and device drivers combine and compare the signals or let a state machine do the combination.
A Different State
There is at least one different way to solve the traffic-light control problem, which involves modeling the state machines as two parallel regions in the same top-level state machine. This has the benefit that we can view the complete solution as a system built up of separate semi-independent components. Space does not permit a full commentary here, but you can see the solution at: iar.com/website1/1.0.1.0/484/1/.
In all cases, designers should aim to keep things as simple as possible. A graphical design tool such as IAR visualSTATE provides a way to raise the abstraction level above hardware details and to generate code, perform tests and simulations, and use model-checking capabilities.
Tweet This
4 
