Introduction

Finite State Machines (FSM) are a way to model and design computer programs and sequential logic circuits. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states, its initial state, and the triggering condition for each transition.

Example

Consider a simple program whose sole purpose is to match, given a binary string, all binary strings that contain 010 as a substring. Some strings in this set include . We can follow the following procedure:

Scan the input value from left to right
If the current bit is a '0', then move on. and otherwise go back to the beginning.
If the next bit read is a '1', then move on, and otherwise go back to the beginning
If the next bit read is a '0', then produce true, otherwise go back to the beginning
Otherwise if there is no more input, and we have not matched 010, produce false

This only scans the input value once, since we read it only in one pass, and gives us linear runtime efficiency.

We can abstract this sort of decision-making process into a graph. Every state in the program is represented as a circle, and transitions between states can be represented by drawing unidirectional arrows between them, labelled with what the transition is. In the above example, states might be partial matches we have matched so far, and state transitions might be labelled by the next bit that is read. This sort of program is known as a state machine. States are the individual configurations of the program based on the inputs seen, and the diagrams we draw are called deterministic finite automata (or DFAs).

A circle within a circle (or a circle with a double border) accepts—it represents a state that, if the input ends there, we can simply accept it as valid, and we can use it as an end state. A circle with an arrow pointing into it from the left represents the start state. The * on the final state denotes any other value in the language (ie. all the valid inputs, which is either 0 or 1, in this case).

Take some time to convince yourself that this graph representation of an automata is the same as the algorithm presented above. Applications of Finite State Machines

Well, whoop-de-doo, that's great and all, but how does matching binary strings relate to writing firmware for a solar car? Recall our earlier definition of a Finite State Machine:

A particular FSM is defined by a list of its states, its initial state, and the triggering condition for each transition.

For the majority of the boards that we write, they all have a predetermined set of states, an initial state, and input conditions (or events) that trigger a transition into a new state. This allows us to easily keep track of the possible interactions between events that are processed, and the firmware's response to a particular event, and guarantees that we can trace the program's flow. They organize complex code, and disect complex set-flag-here-and-test-there spaghetti-code into a matrix of states and events that can be exhaustively examined, debugged and proven.

Pretty much every embedded system used for a consumer electronics device is driven by a state machine. They are really fairly fundamental to embedded development. Moreover, with a state machine, you can easily enforce invariants—if you're in state X, then you know categorically that preconditions have been met (which can help simplify debugging where things went wrong).

Consider the Lights board. When the Lights board receives an appropriate message, it must respond to that event, and perform the appropriate action. Code can quickly become messy, when we have to keep track of all the individual possible light on/off combinations that a driver would want enabled. But with a state machine, we can just check for what to do when we receive an event in the current state we are in, and then transition to the next state. So at its simplest form, when we have an event, say "turn left blinker on", we transition to the "left blinker on" state, and remain in that state until we receive the appropriate event to transition back to the "left blinker off" state.