Top 10 State Machine Design Patterns

Are you tired of writing spaghetti code that's hard to maintain and debug? Do you want to make your code more modular, reusable, and testable? If so, you should consider using state machines in your software design.

A state machine is a mathematical model that describes the behavior of a system in terms of a finite set of states, transitions between those states, and actions that occur when those transitions happen. State machines are used in many domains, such as control systems, communication protocols, user interfaces, and game engines.

In this article, we'll explore the top 10 state machine design patterns that you can use to improve the quality and efficiency of your code. We'll cover the following topics:

1. Simple State Machine
2. Hierarchical State Machine
3. Orthogonal State Machine
4. Concurrent State Machine
5. Mealy Machine
6. Moore Machine
7. Deterministic Finite Automaton
8. Non-Deterministic Finite Automaton
9. Pushdown Automaton
10. Turing Machine

1. Simple State Machine

The simple state machine is the most basic form of a state machine. It consists of a finite set of states and transitions between those states. Each transition is triggered by an event and may have an associated action.

For example, consider a traffic light that has three states: green, yellow, and red. When the light is green, cars can go. When the light is yellow, cars should slow down. When the light is red, cars should stop. The transitions between these states are triggered by a timer or a sensor that detects the presence of cars.

stateDiagram-v2
    [*] --> Green
    Green --> Yellow: Timer
    Yellow --> Red: Timer
    Red --> Green: Timer

In this diagram, the [*] state represents the initial state, which is green. The arrows represent the transitions, and the labels on the arrows represent the events that trigger those transitions. The actions associated with each transition are not shown in this diagram.

2. Hierarchical State Machine

The hierarchical state machine is a state machine that has nested states. Each state can have its own set of sub-states and transitions. This allows you to model complex systems with multiple levels of abstraction.

For example, consider a vending machine that has three states: idle, selecting, and dispensing. When the machine is idle, it waits for the user to insert coins. When the user selects a product, the machine enters the selecting state and displays the available options. When the user confirms the selection, the machine enters the dispensing state and dispenses the product.

stateDiagram-v2
    [*] --> Idle
    Idle --> Selecting: Coin Inserted
    Selecting --> Dispensing: Product Selected
    Dispensing --> Idle: Product Dispensed
    Selecting --> Idle: Cancel

In this diagram, the [*] state represents the initial state, which is idle. The Selecting state has two sub-states: Product Selection and Cancel. The Dispensing state has a sub-state Product Dispensing. The transitions between the states are triggered by events, such as Coin Inserted, Product Selected, and Cancel.

3. Orthogonal State Machine

The orthogonal state machine is a state machine that has multiple independent states that can coexist at the same time. Each state can have its own set of sub-states and transitions. This allows you to model systems that have multiple concurrent activities.

For example, consider a robot that has three orthogonal states: navigation, manipulation, and perception. The navigation state controls the movement of the robot. The manipulation state controls the manipulation of objects. The perception state controls the perception of the environment.

stateDiagram-v2
    [*] --> Navigation
    Navigation --> Manipulation: Object Detected
    Navigation --> Perception: Obstacle Detected
    Manipulation --> Navigation: Object Grasped
    Perception --> Navigation: Obstacle Avoided

In this diagram, the [*] state represents the initial state, which is navigation. The Navigation state has two sub-states: Moving and Stopped. The Manipulation state has a sub-state Grasping. The Perception state has a sub-state Sensing. The transitions between the states are triggered by events, such as Object Detected, Obstacle Detected, and Object Grasped.

4. Concurrent State Machine

The concurrent state machine is a state machine that has multiple independent states that can execute concurrently. Each state can have its own set of sub-states and transitions. This allows you to model systems that have multiple parallel activities.

For example, consider a game that has three concurrent states: gameplay, audio, and graphics. The gameplay state controls the game logic. The audio state controls the sound effects. The graphics state controls the visual effects.

stateDiagram-v2
    [*] --> Gameplay
    Gameplay --> Audio
    Gameplay --> Graphics
    Audio --> Gameplay
    Graphics --> Gameplay

In this diagram, the [*] state represents the initial state, which is gameplay. The Audio and Graphics states can execute concurrently with the Gameplay state. The transitions between the states are not triggered by events, but rather by the completion of the activities.

5. Mealy Machine

The Mealy machine is a state machine that has outputs associated with transitions. The outputs are a function of the current state and the input that triggers the transition. This allows you to model systems that have complex behaviors that depend on the context.

For example, consider a door that has two states: open and closed. When the door is open, it emits a sound. When the door is closed, it emits a different sound.

stateDiagram-v2
    [*] --> Closed: Sound 1
    Closed --> Open: Push
    Open --> Closed: Pull: Sound 2

In this diagram, the [*] state represents the initial state, which is closed. The transitions between the states are triggered by events, such as Push and Pull. The labels on the arrows represent the outputs associated with the transitions, such as Sound 1 and Sound 2.

6. Moore Machine

The Moore machine is a state machine that has outputs associated with states. The outputs are a function of the current state only. This allows you to model systems that have simple behaviors that depend only on the current state.

For example, consider a traffic light that has three states: green, yellow, and red. When the light is green, it emits a green light. When the light is yellow, it emits a yellow light. When the light is red, it emits a red light.

stateDiagram-v2
    [*] --> Green: Green Light
    Green --> Yellow: Timer
    Yellow --> Red: Timer
    Red --> Green: Timer
    Yellow --> Flashing Yellow: Timer
    Flashing Yellow --> Red: Timer

In this diagram, the [*] state represents the initial state, which is green. The transitions between the states are triggered by a timer. The labels on the states represent the outputs associated with the states, such as Green Light.

7. Deterministic Finite Automaton

The Deterministic Finite Automaton (DFA) is a state machine that recognizes a regular language. A regular language is a set of strings that can be generated by a regular expression. A DFA has a finite set of states, a finite set of input symbols, a transition function, an initial state, and a set of accepting states.

For example, consider a DFA that recognizes the language of binary numbers that are divisible by 3. The input symbols are 0 and 1. The transition function is defined as follows:

graph TD
    A --> B[0]
    A --> C[1]
    B --> D[0]
    B --> E[1]
    C --> F[0]
    C --> G[1]
    D --> B
    E --> C
    F --> G
    G --> F

In this diagram, the states represent the remainder of the binary number when divided by 3. The initial state is 0, which means that the empty string is accepted. The accepting states are 0 and 11, which means that the binary numbers that are divisible by 3 are accepted.

8. Non-Deterministic Finite Automaton

The Non-Deterministic Finite Automaton (NFA) is a state machine that recognizes a regular language. A NFA has a finite set of states, a finite set of input symbols, a transition function, an initial state, and a set of accepting states. The difference between a NFA and a DFA is that a NFA can have multiple transitions for the same input symbol from the same state.

For example, consider a NFA that recognizes the language of binary numbers that contain at least one 1. The input symbols are 0 and 1. The transition function is defined as follows:

graph TD
    A --> B[0]
    A --> C[1]
    B --> B[0]
    B --> C[1]
    C --> C[1]
    C --> D[0]

In this diagram, the states represent the presence or absence of the symbol 1 in the binary number. The initial state is 0, which means that the empty string is not accepted. The accepting state is 1, which means that the binary numbers that contain at least one 1 are accepted.

9. Pushdown Automaton

The Pushdown Automaton (PDA) is a state machine that recognizes a context-free language. A context-free language is a set of strings that can be generated by a context-free grammar. A PDA has a finite set of states, a finite set of input symbols, a finite set of stack symbols, a transition function, an initial state, an initial stack symbol, and a set of accepting states.

For example, consider a PDA that recognizes the language of balanced parentheses. The input symbols are ( and ). The stack symbols are ( and Z. The transition function is defined as follows:

graph TD
    A --> B[0, Z/Z(]
    B --> C[(, (/(]
    C --> B
    C --> D[), (/Z]
    D --> C
    D --> E[), (/Z]
    E --> D

In this diagram, the states represent the number of open and closed parentheses seen so far. The stack symbols represent the remaining open parentheses that have not been matched with a closed parenthesis. The initial state is 0, which means that the empty string is not accepted. The initial stack symbol is Z, which means that the stack is initially empty. The accepting state is 0, which means that the balanced parentheses are accepted.

10. Turing Machine

The Turing Machine (TM) is a state machine that recognizes a recursively enumerable language. A recursively enumerable language is a set of strings that can be generated by a Turing machine. A TM has a finite set of states, a finite set of input symbols, a finite set of tape symbols, a transition function, an initial state, an initial tape, and a set of accepting states.

For example, consider a TM that recognizes the language of palindromes. The input symbols are a, b, and the blank symbol. The tape symbols are a, b, the blank symbol, and the marker symbol #. The transition function is defined as follows:

graph TD
    A --> B[a/#, R]
    A --> B[b/#, R]
    A --> F[#, #, R]
    B --> C[a/a, R]
    B --> C[b/b, R]
    C --> D[#, #, L]
    C --> E[a/a, L]
    C --> E[b/b, L]
    D --> F[#, #, R]
    E --> A

In this diagram, the states represent the position of the head on the tape and the contents of the tape. The input string is written on the tape with the marker symbol # in the middle. The initial state is A, which means that the head is at the left end of the tape. The accepting state is F, which means that the palindrome has been recognized.

Conclusion

State machines are a powerful tool for software design. They allow you to model complex systems in a modular, reusable, and testable way. By using the top 10 state machine design patterns, you can improve the quality and efficiency of your code. So, what are you waiting for? Start using state machines today and see the difference for yourself!

Additional Resources