Finite-State Machine

This post introduces the finite-state machine.

You have probably seen code like this.

if is_loading:
    ...
elif has_error and not is_loading:
    ...
elif is_submitted and has_error:
    ...

Three boolean flags give you eight combinations. Only three or four of them mean anything, and the rest are combinations that must never happen.

The problem is that the “must never happen” part is written nowhere in the code. It lives in the developer’s head.

A finite-state machine approaches this from the opposite direction. You enumerate every possible state, and you allow only the paths between them.

What is a finite-state machine?

A finite-state machine (FSM) is a model of computation that sits in exactly one of a finite number of states.

When it reads an input, a fixed rule moves it to another state. That move is called a transition.

It has five components.

Take a subway turnstile. Insert a coin while it is locked and it unlocks; push through while it is unlocked and it locks again.

What happens if you push while it is locked? Nothing happens, and it stays locked.

Drawing that “nothing happens” explicitly is the whole point of an FSM. In the flag version, that case was simply absent.

The state transition table

The same diagram can be written as a table, with states as rows and inputs as columns.

Notice that there is not a single empty cell. Two states and two inputs give exactly four cells, and the machine is only complete when all of them are filled.

An empty cell at design time is behaviour you have not decided yet. The table catches it before any of it becomes code.

A short history

The roots go back to 1943, when McCulloch and Pitts built a model to describe neural networks mathematically.

Mealy in 1955 and Moore in 1956 each formalised machines that produce output, and in the same year Kleene proved that regular expressions and finite automata have the same expressive power.

In 1959 Rabin and Scott introduced nondeterministic finite automata, which produced the formulation textbooks still use today. Both received the Turing Award for this work in 1976.

Acceptors and transducers

FSMs split into two broad families depending on how they produce output.

Acceptors

An acceptor reads the input to the end and answers only yes or no.

If the state it lands in is a final state, the input is accepted; otherwise it is rejected. This is exactly how a regular expression tests a string.

The machine below accepts strings made of zero or more a characters followed by a single b.

Q2 is a state you can never leave once you fall into it. This is called a dead state: the condition has already been violated, so no amount of remaining input can change the answer.

Transducers: Moore and Mealy

A transducer produces output as it moves between states. Where that output is attached splits it into two models.

A Moore machine produces output based only on the current state. The output hangs off the state like a label.

A Mealy machine produces output based on the state and the input together. The output hangs off the arrow rather than the state.

Which one is better? Their expressive power is identical, and each converts into the other.

The difference is timing. Moore settles its output after the state changes, so it lags by one step, while Mealy emits output the moment input arrives and tends to need fewer states.

In hardware design that one step matters. Moore is generally preferred in circuits because its timing is easier to predict.

Determinism and nondeterminism

Every machine so far had exactly one next state for a given state and input. Those are deterministic finite automata, or DFAs.

Nondeterministic finite automata

A nondeterministic finite automaton (NFA) drops that restriction. A single input may lead to several states, or to none at all.

It may even move between states without reading any input, through what is called an ε-transition.

So is an NFA more powerful than a DFA? It feels like it should be, but the answer is no.

The powerset construction

Every NFA can be converted into an equivalent DFA, through what is known as the subset or powerset construction.

The idea is simple. You take “the set of states the NFA could currently be in” and treat that whole set as a single DFA state.

An NFA that might be in either Q1 or Q3 becomes a DFA sitting in one state you can just call Q13.

The cost is state count. If the NFA has n states, there are up to 2^n subsets, so in the worst case the DFA blows up exponentially. That is why many production engines simulate the NFA directly instead.

The relationship with regular expressions

As mentioned above, Kleene proved that regular expressions and finite automata describe the same thing.

That is why regular expression engines generally work in this order.

regular expression → NFA → (optionally) DFA → matching

The standard way to turn a regular expression into an NFA is Thompson’s construction, published by Ken Thompson in 1968. It defines a small NFA fragment for each operator and assembles them into the whole.

Three ways to implement one

Now down to actual code. Here is that turnstile implemented three different ways.

1. Conditionals

The approach that comes to mind first.

def transition(state: str, event: str) -> str:
    if state == "LOCKED":
        if event == "coin":
            return "UNLOCKED"
        return "LOCKED"

    if state == "UNLOCKED":
        if event == "push":
            return "LOCKED"
        return "UNLOCKED"

    raise ValueError(f"unknown state: {state}")

With two or three states, nothing beats this. No dependencies, and it reads fine.

Once states multiply, though, the nesting deepens and a missing combination will not stand out. The flag problem from the opening returns in a different shape.

2. A transition table

This expresses the transition function as data rather than code.

TRANSITIONS = {
    ("LOCKED",   "coin"): "UNLOCKED",
    ("LOCKED",   "push"): "LOCKED",
    ("UNLOCKED", "coin"): "UNLOCKED",
    ("UNLOCKED", "push"): "LOCKED",
}

def transition(state: str, event: str) -> str:
    return TRANSITIONS[(state, event)]

The transition table drawn earlier has become the code itself. An empty cell in the table means a missing key, which surfaces immediately as an exception.

You can also move the rules into JSON or YAML and change them without touching code. Walking the table to find unreachable states is easy to add as a validation step.

The catch is side effects. If a transition has to run one, a plain table is not enough and you end up storing functions as the values.

3. The state pattern

Give each state its own class and let each class own its transitions.

class Locked:
    def coin(self): return Unlocked()
    def push(self): return self

class Unlocked:
    def coin(self): return self
    def push(self): return Locked()

The branching disappears, and adding a new state does not require touching the existing classes.

If each state has its own entry and exit work, this structure is the cleanest. You put on_enter and on_exit on each class and you are done.

The trade-off is that five states means five classes. Seeing the full set of transitions means opening five files.

Which one to pick

What an FSM cannot do

An FSM is not a universal tool. What it cannot do is precisely what characterises the model.

It cannot count

Can an FSM check whether parentheses are balanced?

If the nesting depth is bounded, yes. Assign a state to depth 1, depth 2, depth 3, and you are done.

If the depth is unbounded, no. The number of states is finite while the depths you would have to count are not.

That job needs a stack, and the model with a stack attached is the pushdown automaton.

This is the basis for the old advice about not parsing HTML with regular expressions. Nested structure is not a regular language to begin with.

State explosion

The second limit shows up far more often in practice.

Every independent concern you add multiplies the state count. Three connection states and three authentication states on one flat FSM already need nine.

Add four playback states and you are at thirty-six. That is not a diagram anyone can draw.

The answer is to stack states into a hierarchy. UML state machines nest states inside states and separate independent concerns into orthogonal regions.

When a flat FSM diagram grows past what you can read, it usually means two independent concerns have been mixed into one machine. Splitting it into two machines is the right answer most of the time.

Where they are already in use

FSMs are not confined to a theory course. They are already sitting in nearly everything.

• Lexers and tokenizers: the thing a compiler uses to cut source into tokens is a DFA.
• Regular expression engines: as above, expressions are converted into finite automata and run.
• Network protocols: a TCP connection moves between states like LISTEN, SYN_SENT, ESTABLISHED, and TIME_WAIT. The RFC ships the state diagram itself.
• UI state: forms and checkout flows with fixed steps are safer as state machines than as flags.
• Game AI: patrol, chase, attack, flee. The classic implementation for NPC logic with clearly separated behaviours.
• Hardware control: traffic lights, elevators, vending machines, and CPU control units are all designed as state machines.

Practice problems

LeetCode 65. Valid Number

Validating a numeric format. Solved with conditionals it sprawls forever, but drawing the transition table first makes it far easier. There is no better FSM exercise.

LeetCode 8. String to Integer (atoi)

Handling whitespace, sign, digits, and everything else in order. It organises nicely into a four-state transition table.

LeetCode 393. UTF-8 Validation

Checking whether a byte sequence is valid UTF-8. Treat “bytes remaining” as the state and it becomes a state machine naturally.

References

• Finite-state machine — Wikipedia
• Nondeterministic finite automaton — Wikipedia
• Powerset construction — Wikipedia
• Thompson’s construction — Wikipedia
• Mealy machine — Wikipedia
• Moore machine — Wikipedia
• UML state machine — Wikipedia
• RFC 9293: Transmission Control Protocol (TCP) — connection state diagram