Finite state machines explained

What a finite state machine is, how to draw its state transition diagram and table, and Mealy vs Moore, shown on a traffic light and a robot that searches, approaches and comes home. Change the numbers, press Run, and see what a missing transition does.

Guidefree, runs in your browser

A finite state machine is a system that is always in exactly one of a small number of states, and moves from one state to another when something happens. A traffic light is one: it is red, or red and amber, or green, or amber, and it moves on when its time is up. So are lifts, vending machines, washing machines and the behaviour of nearly every robot. On this page a small robot runs four state machines, from waiting at a traffic light to finding a marker and bringing the news home, and each demo below is a real program you can change and run.

In the overhead view of most demos, the robot's trail is coloured by the state it was in, so you can see where each state began and ended. The chart underneath numbers the states (0 for the first, 1 for the second and so on) and shows which one the machine was in at every moment.

The idea in one loop

state = the start state
every tick:
    read the sensors and turn them into one input
    look up (state, input) to find the next state
    do whatever that transition says
    state = the next state

A finite state machine has:

• a finite set of states, such as SEARCH, APPROACH and STOP;
• a set of inputs it can react to, such as "marker in view" or "time up";
• a start state, where every run begins;
• transitions: for each state and input, the state to move to next;
• usually some output: what the machine does, such as drive, stop or light a lamp.

The machine remembers nothing except which state it is in. That is the whole point. Instead of a tangle of flags and counters, the program has one variable, state, and every question about what the robot should do next starts with "which state am I in?".

The state transition diagram

Before writing a state machine, draw it. In a state transition diagram each state is a circle and each transition is an arrow, labelled with the input that causes it. The start state has an arrow coming in from nowhere. Here is a UK traffic light:

The same machine as a state transition table, one row per transition:

The diagram and the table hold exactly the same information. The diagram is easier for a person to follow; the table is easier to check (is there a row for every state and every input?) and it goes straight into a program as a dictionary.

A traffic light and a robot

Two state machines at once. The light runs the diagram above. The robot has three states of its own: DRIVE up to the stop line, WAIT there while the light is not green, and GONE once it is over the line, when the light no longer matters to it.

from bugbot import *
connect()

# change these numbers and press Run
SECONDS = {"RED": 6, "RED+AMBER": 1,
           "GREEN": 4, "AMBER": 2}
SPEED = 50           # percent

# the light: each state lasts a while, then moves on
NEXT = {"RED": "RED+AMBER", "RED+AMBER": "GREEN",
        "GREEN": "AMBER", "AMBER": "RED"}
# which lamps are lit (red, amber, green) depends
# on the state and nothing else
LIT = {"RED": (1, 0, 0), "RED+AMBER": (1, 1, 0),
       "GREEN": (0, 0, 1), "AMBER": (0, 1, 0)}
LAMPS = [("red", 72), ("orange", 66), ("green", 60)]
LINE = 55            # the stop line, cm up the mat

def show(light):
    for (colour, y), on in zip(LAMPS, LIT[light]):
        shade = colour if on else "#333333"
        draw(colour, [(70, y)], shade, "squares", 5)

draw("line", [(35, LINE), (65, LINE)], "white", "line")
light = "RED"
changed = 0.0
robot = "DRIVE"
forward(SPEED)
while clock() < 20:
    # the light moves on when its time is up
    if clock() - changed >= SECONDS[light]:
        light = NEXT[light]
        changed = clock()
        print(round(clock(), 1), "light:", light)
    show(light)
    # the robot: read the inputs, then one transition
    y = 20 + position()[1]        # its middle
    at_line = y > LINE - 8
    was = robot
    if robot == "DRIVE":
        if at_line and light != "GREEN":
            robot = "WAIT"
            stop()
        elif y > LINE - 4:
            robot = "GONE"
    elif robot == "WAIT":
        if light == "GREEN":
            robot = "GONE"
            forward(SPEED)
    elif robot == "GONE" and y > 85:
        break
    if robot != was:
        print(round(clock(), 1), "robot:", robot,
              "at y =", round(y))
    plot("light", ["RED", "RED+AMBER", "GREEN",
                   "AMBER"].index(light))
    plot("robot", ["DRIVE", "WAIT",
                   "GONE"].index(robot))
    wait(0.1)
stop()

On the chart, the light counts 0 (red), 1 (red and amber), 2 (green), 3 (amber), and the robot 0 (drive), 1 (wait), 2 (gone). The robot drives at about 9 cm/s, reaches the line at 3.3 s, and stops with its front about 2 cm short of it. It sits in WAIT, doing nothing, until the light's state changes to GREEN at 7.0 s. That one input moves it to GONE, and it drives on to the top of the mat, where the program ends at 11.1 s. The light turns amber at 11.0 s, but by then the robot is in GONE, and GONE has no transition that looks at the light.

Try "RED": 1. The light is green by 2.0 s, and the robot crosses the line at 3.7 s without stopping: it never enters WAIT. Try "RED": 3 and it waits for only 0.7 s.

Notice what the program does not have: no flag called stopped_already, no counter of how many times the light has changed. The robot's state says everything it needs to know. GONE earns its place too. Without it, the robot would still be in DRIVE after crossing, at_line would still be true, and the next amber light would stop it in the middle of the junction. Take GONE out of this program and that is what happens: the amber at 11.0 s stops the robot about 30 cm past the line.

A transition table in Python

The robot in the last demo was written as if and elif, one branch per state. For a machine with more inputs it is safer to write the transition table itself into the program. This robot has to find marker 4, drive up to it and stop. Its camera gives one of three inputs each tick: none (the marker is not in view), far (in view, more than 15 cm away) or near (15 cm or closer).

Two states that can move and three inputs make six rows. Writing them all out makes you answer the awkward questions, such as: what if the marker drops out of view while the robot is driving at it? The row (APPROACH, none) says: go back to searching. A chain of if statements written in a hurry often has no answer to that at all.

In Python the table is a dictionary. Each key is a pair (state, input) and each value is a pair (next state, output), so one lookup does a whole transition.

from bugbot import *
connect()

# change this number and press Run
NEAR = 15        # cm from the marker: close enough

# (state, input): (next state, output)
table = {
    ("SEARCH", "none"): ("SEARCH", "spin"),
    ("SEARCH", "far"): ("APPROACH", "drive"),
    ("SEARCH", "near"): ("STOP", "halt"),
    ("APPROACH", "none"): ("SEARCH", "spin"),
    ("APPROACH", "far"): ("APPROACH", "drive"),
    ("APPROACH", "near"): ("STOP", "halt"),
}

def sense():
    # turn the camera into one input symbol
    tags = [t for t in apriltags() if t[0] == 4]
    if not tags:
        return "none", 0
    plot("marker cm / 10", tags[0][3] / 10)
    if tags[0][3] <= NEAR:
        return "near", 0
    return "far", (tags[0][1] - 160) * 120 / 320

def act(output, steer):
    if output == "spin":
        turn_right(40)
    elif output == "drive":
        drive(60, 0, steer * 3)
    else:
        stop()

COLOUR = {"SEARCH": "yellow", "APPROACH": "blue"}
trail = {"SEARCH": [], "APPROACH": []}
set_cv("apriltag")
state = "SEARCH"
while state != "STOP" and clock() < 30:
    symbol, steer = sense()
    new, output = table[(state, symbol)]
    act(output, steer)
    if new != state:
        print(round(clock(), 1), state, "->", new)
    state = new
    plot("state", ["SEARCH", "APPROACH",
                   "STOP"].index(state))
    if state in trail:
        x, y = position()
        trail[state].append((50 + x, 50 + y))
        draw(state, trail[state], COLOUR[state])
    wait(0.1)
stop()

The loop never changes, whatever the machine. Only the table does: to add a state, you add rows. sense() is the only place that looks at the camera, and act() the only place that drives the motors, so the table itself is plain data you could show a teammate to check. The robot comes to rest 12 cm from the marker; the extra 2 cm is the robot coasting after stop().

Two things to try, both of which break it:

• Delete the row ("APPROACH", "none") and run it. Nothing changes: in this run the marker never leaves the camera's view, so that row is never used. Now also set NEAR = 0. The robot drives right over the marker at 5.5 s, loses sight of it, and the program stops with KeyError: ('APPROACH', 'none'). A missing row in a table fails loudly, at the moment the case turns up. A missing elif does whatever the motors were last told to do.
• Put the row back and keep NEAR = 0. No reading is ever 0 cm or less, so the input near can never arrive and STOP can never be reached. The robot drives over the marker, goes back to SEARCH, and then sits almost on top of it, spinning, catching sight of it for a moment now and then. It is still in SEARCH when the program gives up at 30 s. A state with no way in is as much a bug as a state with no way out.

What goes wrong: a transition that fires too soon

A robot that wanders round a room without hitting the walls has two states: FORWARD, and TURN on the spot. It starts turning when the depth sensor reads less than 25 cm. When should it stop turning?

The obvious answer is "when the reading is more than 25 cm again". Here it is.

from bugbot import *
connect()

# change these numbers and press Run
TOO_CLOSE = 25   # cm: start turning below this
CLEAR = 25       # cm: stop turning above this

COLOUR = {"FORWARD": "yellow", "TURN": "red"}
trail = {"FORWARD": [], "TURN": []}
state = "FORWARD"
changes = 0
while clock() < 25:
    d = distance()
    was = state
    if state == "FORWARD" and d < TOO_CLOSE:
        state = "TURN"
    elif state == "TURN" and d > CLEAR:
        state = "FORWARD"
    if state != was:
        changes = changes + 1
    if state == "FORWARD":
        forward(60)
    else:
        turn_right(40)
    x, y = position()
    trail[state].append((50 + x, 20 + y))
    draw(state, trail[state], COLOUR[state])
    plot("turning", 1 if state == "TURN" else 0)
    plot("bumped", 1 if bumped() else 0)
    wait(0.1)
stop()
print("changes of state:", changes)

The robot turns only until the reading reaches 26 cm, often a turn of 13 degrees or less, and then drives on at nearly the same angle. A second or so later the reading is under 25 again and it turns a little more. The red patches on the trail, where it turned on the spot, come close together, and the chart's "turning" line flickers between 0 and 1. The small turns leave it running along the walls at a shallow angle, and from 18.1 to 19.4 s the "bumped" line shows it rubbing along the right-hand wall.

The fix is two thresholds: start turning below 25 cm, but keep turning until the reading is above 40.

from bugbot import *
connect()

# change these numbers and press Run
TOO_CLOSE = 25   # cm: start turning below this
CLEAR = 40       # cm: stop turning above this

COLOUR = {"FORWARD": "yellow", "TURN": "red"}
trail = {"FORWARD": [], "TURN": []}
state = "FORWARD"
changes = 0
while clock() < 25:
    d = distance()
    was = state
    if state == "FORWARD" and d < TOO_CLOSE:
        state = "TURN"
    elif state == "TURN" and d > CLEAR:
        state = "FORWARD"
    if state != was:
        changes = changes + 1
    if state == "FORWARD":
        forward(60)
    else:
        turn_right(40)
    x, y = position()
    trail[state].append((50 + x, 20 + y))
    draw(state, trail[state], COLOUR[state])
    plot("turning", 1 if state == "TURN" else 0)
    plot("bumped", 1 if bumped() else 0)
    wait(0.1)
stop()
print("changes of state:", changes)

This gap between the "go in" and the "come out" conditions is called hysteresis. It is why a thermostat does not click on and off every second, and why a well-made robot does not dither on the edge between two states. Whenever a transition into a state and the transition back out look at the same sensor, give them different thresholds. Try CLEAR = 60: 6 changes of state, and still no bumps.

Adding a state: rescue

A machine grows one state at a time. This robot has to find marker 9, drive up to it, then come home, without touching the box. That is the search and approach machine from before with one more state, HOME, and a final state, DONE, where the loop ends. Each state is one branch of the if, and each transition is one line that sets state.

from bugbot import *
import math
connect()

# change these numbers and press Run
NEAR = 12        # cm from the marker: turn for home
HOME = 8         # cm from the start: done

def wrapped(h):
    return (h + 180) % 360 - 180

def go_to(x, y, speed=60):
    # slide towards (x, y) without turning
    px, py = position()
    a = math.degrees(math.atan2(x - px, y - py))
    a = math.radians(wrapped(a - heading()))
    drive(speed * math.cos(a), speed * math.sin(a),
          wrapped(0 - heading()) * 3)

def tag9():
    tags = [t for t in apriltags() if t[0] == 9]
    return tags[0] if tags else None

COLOUR = {"SEARCH": "yellow", "APPROACH": "blue",
          "HOME": "green"}
trail = {s: [] for s in COLOUR}
set_cv("apriltag")
state = "SEARCH"
while state != "DONE" and clock() < 40:
    tag = tag9()
    was = state
    if state == "SEARCH":
        if tag:
            state = "APPROACH"
        else:
            turn_right(40)
    elif state == "APPROACH":
        if tag and tag[3] < NEAR:
            state = "HOME"
        elif tag:
            steer = (tag[1] - 160) * 120 / 320
            drive(60, 0, steer * 3)
        else:
            state = "SEARCH"
    elif state == "HOME":
        x, y = position()
        if math.hypot(x, y) < HOME:
            state = "DONE"
        else:
            go_to(0, 0)
    if state != was:
        print(round(clock(), 1), was, "->", state)
    plot("state", ["SEARCH", "APPROACH", "HOME",
                   "DONE"].index(state))
    if state in trail:
        x, y = position()
        trail[state].append((20 + x, 20 + y))
        draw(state, trail[state], COLOUR[state])
    wait(0.1)
stop()

Look at the shape of the program: helpers at the top, one state variable, one loop, one branch per state, and transitions as plain conditions. That is how behaviour code is written for much larger robots; they have more states and more sensors, not a different idea. Try NEAR = 30: the robot turns for home sooner and is done at 13.3 s.

Mealy and Moore machines

A machine that produces output as it runs comes in two kinds, and this page has both.

• In a Moore machine the output belongs to the state. The traffic light is one: in RED the red lamp is lit, whatever else is happening. The LIT dictionary in the first demo looks up the lamps from the state alone.
• In a Mealy machine the output belongs to the transition, so it depends on the state and the input together. The search controller is one: from SEARCH, the input none gives spin but far gives drive. Each arrow is labelled input/output.

Anything one kind can do, the other can do too, but a Moore machine may need more states. A classic small Mealy machine is an edge detector for a bump sensor that reads 1 while pressed. It should output 1 once per bump, on the tick the input changes from 0 to 1:

Traced from LOW on the input 0110111:

Two bumps, each reported once, and seven inputs give seven outputs. A Moore version needs three states, because "the tick of the bump" has to be a state of its own to carry the output 1.

Recognisers, accepting states and DFAs

In computer science the same machine is used to answer yes or no about a string of symbols. A machine with no output, read to the end of its input, accepts the string if it finishes in an accepting state (drawn as a double circle) and rejects it otherwise. This one accepts binary strings with an even number of 1s:

A 0 changes nothing, so it loops back to the same state; a 1 swaps between EVEN and ODD. The machine never counts the 1s. It only remembers whether the count so far is odd or even, and two states are enough to hold that. To trace 1011: EVEN, then ODD, ODD, EVEN, ODD. It ends in ODD, so 1011 is rejected, which is right: it has three 1s.

Both kinds of machine fit in a few lines of Python:

# a recogniser: an even number of 1s?
table = {
    ("EVEN", "0"): "EVEN",
    ("EVEN", "1"): "ODD",
    ("ODD", "0"): "ODD",
    ("ODD", "1"): "EVEN",
}
accepting = {"EVEN"}

def accepts(text):
    state = "EVEN"
    for symbol in text:
        state = table[(state, symbol)]
    return state in accepting

# a Mealy machine: output 1 on a rising edge
edge = {
    ("LOW", "0"): ("LOW", "0"),
    ("LOW", "1"): ("HIGH", "1"),
    ("HIGH", "0"): ("LOW", "0"),
    ("HIGH", "1"): ("HIGH", "0"),
}

def translate(inputs):
    state, outputs = "LOW", ""
    for symbol in inputs:
        state, out = edge[(state, symbol)]
        outputs = outputs + out
    return outputs

print(accepts("1011"), accepts("1001"), accepts(""))
print(translate("0110111"))

It prints False True True, then 0100100. The empty string is accepted because the machine starts in EVEN, and zero 1s is an even number.

A recogniser with exactly one transition for every state and every symbol is a deterministic finite automaton, or DFA. When a diagram leaves some transitions out, the convention is that the input is rejected at once; to make the table complete you add a trap state, a non-accepting state that every symbol loops back to. The strings a DFA accepts form a regular language, the same set of languages that regular expressions describe, and a finite number of states is also the limit of what these machines can do: no FSM can check that brackets are balanced to any depth, because it would need a new state for every level of nesting.

Questions

What is a finite state machine?

It is a model of a system that is always in one of a fixed, finite set of states. It starts in a start state, and each input moves it along a transition to a next state, which can be the same one. It remembers nothing else: the current state is its only memory. It may produce output as it goes (a Mealy or Moore machine) or say at the end whether it accepts its input (a recogniser).

What is an example of a finite state machine?

A traffic light: its states are red, red and amber, green, and amber, and the input "time up" moves it round the ring. Others are a lift (which floor, doors open or shut, going up or down), a vending machine (how much money has been put in), a washing machine's programme, and a robot that searches for a marker, drives to it and stops. Every demo on this page is one.

Why do we use finite state machines?

Because they turn a behaviour into something you can draw, check and test. Each state has one job, each transition has one condition, and a table with a row for every state and input makes you decide what happens in the awkward cases. The program is short, with one state variable instead of a pile of flags, and it is easy to add a state later. They are used in robot behaviour, games, network protocols, user interfaces, digital circuits, and the part of a compiler that splits source code into tokens.

What is the difference between a Mealy and a Moore machine?

In a Moore machine the output depends only on the current state: a traffic light in RED shows red. In a Mealy machine the output is on each transition, so it depends on the state and the input just read, and the arrows are labelled input/output. The two can do the same jobs, but a Moore machine often needs more states, and a Mealy machine's output responds one step sooner.

What is the difference between a DFA and an FSM?

A DFA (deterministic finite automaton) is one particular kind of finite state machine: it has no output, it has accepting states, and it has exactly one transition for every state and input symbol. It reads a string and answers accept or reject. "Finite state machine" is the wider term, and also covers machines with output (Mealy and Moore) and nondeterministic machines (NFAs), which can have several transitions, or none, for the same state and input.

What is a state transition table?

It is the machine written as a table, with one row for each pair of current state and input, giving the next state (and, for a machine with output, the output). It holds exactly the same information as the state transition diagram. A complete table for a machine with 4 states and 3 input symbols has 12 rows. In Python it becomes a dictionary with (state, input) as the key.

How do you draw a state transition diagram?

Draw a circle for each state and name it. Draw an arrow for each transition, from the old state to the new one, and label it with the input that causes it (for a Mealy machine, input/output). An input that leaves the state unchanged is an arrow that loops back to the same circle. Mark the start state with an arrow from nowhere, and draw accepting states with a double circle.

How do you write a state machine in Python?

Keep the state in one variable, such as state = "SEARCH", and run a loop. Each time round, read the inputs, then either use if state == ... and elif with one branch per state, or look up table[(state, symbol)] in a dictionary that holds the transition table, and set state to the next state. The demos on this page show both styles on a robot; the table style is safer for bigger machines, because a missing row raises a KeyError instead of silently doing the wrong thing.

Why does my state machine flicker between two states?

Because the condition that takes it into a state and the condition that takes it back out use the same threshold. Sensor noise, or the robot's own movement, pushes the reading back and forth across that one number. Use two thresholds with a gap between them (hysteresis): in the wander demo on this page, turning below 25 cm and stopping at 25 cm gave 24 changes of state and a scrape along the wall; stopping at 40 cm gave 8 and no bumps.

What is a trap state?

A non-accepting state that every input loops back to, so once the machine falls in it can never get out. It is used to complete a transition table when a diagram leaves out some transitions: those inputs go to the trap state, and the string is rejected.

What can a finite state machine not do?

It cannot count without limit, because its only memory is which of its finite states it is in. So no FSM can check that a string has the same number of 0s as 1s, or that brackets are balanced to any depth. Those need a machine with more memory, such as a pushdown automaton or a Turing machine.

Are finite state machines on the GCSE or A level specification?

They are in AQA's A level Computer Science (7517), section 4.4.2.1: state transition diagrams and tables for FSMs with and without output, where the machines with output are Mealy machines only. Questions ask you to trace a machine on an input, turn a diagram into a table or the reverse, and describe in words which strings a machine accepts. The OCR, AQA and Edexcel GCSE specifications do not name them.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. A6.1 Finite state machines Theory of computation, A level
2. A6.2 Mealy machines: FSMs with output Theory of computation, A level
3. 5.2 States Behaviours, Robot club
4. 5.6 Project: rescue Behaviours, Robot club