What is a State Machine?

2023-08-09 | By Maker.io Staff

State machines are among the few theoretical programming concepts that are easy to understand yet incredibly powerful and important when writing various computer programs. While there’s always more to be said about automata theory in general, this article briefly examines finite state machines, which impose a few limitations to keep things simple.

Save States: The Basic Concept of State Machines

The basic concept of state machines can be described in a single sentence: A state machine is ‎any program or device that remembers its current state and then reacts to your input according ‎to its currently stored state. Aside from performing a particular task, state machines can change ‎states depending on input or other factors. One such instance would be after a certain period ‎passes without the device detecting any inputs. In addition, some state machines can also output ‎values to detect, for example, specific input sequences.

A state machine, often referred to as a finite state machine (FSM) in automata theory, is ‎technically a tuple of values. Essentially, the formal description of an FSM consists of its starting ‎state and a tuple for each combination of the current state, input, output, and transition that ‎should be modeled in the system. In simpler terms, you can think of a state machine as a finite ‎‎— albeit potentially very large — table that lists all possible state and input combinations and how ‎the system reacts when receiving a specific input while in a given state.

While you can formally describe FSMs using tables and formulae, you can also represent them ‎graphically using a directed, possibly cyclic graph where each vertex encodes one of the ‎machine’s states, and the edges between the vertices model the state transitions.

An FSM Snack Vending Machine

What is a State Machine? Snack vending machines can be modeled as simple finite state machines.

Don’t worry if the above explanation sounded too complicated. Once the concept behind a state ‎machine becomes apparent, you might notice how many everyday systems and devices you ‎can model using an FSM. Consider, for example, a snack vending machine that lets you buy ‎snacks. The device’s operation is as follows:

The machine should keep track of the balance whenever you insert money and only accepts ‎one-dollar bills and quarters. At any point, you may enter a number between one and twenty-five ‎to select one of the products available for purchase. The machine rejects any other numbers ‎outside of this range. If you enter a valid number, the device checks whether the balance ‎exceeds the selected item’s price. If it does, the machine drops the chosen item and returns any ‎change. If the balance is too low, the machine beeps and displays the item price on its display for ‎five seconds. You can always press the coin return button on the machine to retrieve your ‎balance, and the vending machine starts in an idle state with its balance set to zero.

According to this description, four states exist: idle, drop, return, and info. Additionally, a variable ‎keeps track of your balance. As mentioned, FSMs can be visually represented using graphs. ‎Therefore, we can add four states to the diagram for now:

What is a State Machine? The simple vending machine FSM contains the four states shown in this image.

Note that a double outline typically indicates the initial state of an FSM. However, some drawings ‎may also use an arrow that points toward the initial state yet is not connected to any other nodes. ‎Either way, the edges in an FSM graph model the machine’s transitions between states in ‎reaction to events or user inputs. Therefore, we can model what happens when you select a ‎valid number by adding the following transitions between nodes:

What is a State Machine? The machine’s basic behavior can be modeled by adding a few transitions and conditions.

So, whenever the number is valid and the balance is sufficient, the machine deposits the ‎selected item and returns the remaining balance. Otherwise, it displays the item’s price. Missing ‎transitions indicate that the machine ignores invalid inputs. It’s important to note, however, that ‎the device will remain in either the info or return state indefinitely in the current model, which ‎may be desirable in some applications. In this particular case, the machine should return to the ‎idle state and wait for additional input:

What is a State Machine? The machine should return to its initial state once it finishes a transaction, which is indicated by ‎the edges going back to the idle state from the return, drop, and info states.

The edge going from the return state to the idle node does not have a label, meaning that ‎whenever the machine finishes in the return state, it automatically switches to the idle state.

Finally, remember that the drawing can be refined as much as necessary to model a process. ‎For instance, you could introduce five states to represent five individual beeps. It’s often ‎advisable though to design state machines that abstract the involved steps to a more ‎understandable, coherent process. Adding state machine drawings to represent what happens ‎during some states requiring more details is also possible. An additional diagram for the drop ‎state could, in one example, include nodes for turning a motor 270 degrees counterclockwise to ‎represent further details of what happens during the more general FSM's drop state.

Summary

State machines are a handy introductory concept of automata theory. While this article ‎introduced the essentials of state machines, it didn’t go into the details and nuances of different ‎state machines and how they can be used to model various scenarios.

A finite state machine is any device or program that remembers its current state and performs ‎actions based on that state. These actions may be triggered by user input, external or internal ‎events, or happen automatically.

It’s often advisable for you to keep drawings at a higher level of abstraction whenever practicable. Graphs that are too detailed may be more confusing than helpful. However, introducing additional FSM graphs that model one of the processes in greater detail is also possible.

Have a state machine project in mind? Scheme-it lets you quickly diagram and save your state machine concept, then easily share or collaborate on the design with others.