Mealy machines: FSMs with output

Output on every transition, tracing a Mealy machine, and a search, approach and stop controller for the robot.

A6.2Theory of computationA level25 min

Covers AQA 7517 4.4.2.1 Finite state machines (FSMs) with and without output

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Finite state machines explained

The machines in the last lesson only said yes or no at the end. A robot controller has to do something on every tick: spin, drive, stop. A finite state machine with output produces an output as it goes. In a Mealy machine, the output is produced on each transition, so it depends on both the current state and the input just read.

Labelling transitions with output

A Mealy machine has states, an input alphabet, a start state and a transition function just like before, plus an output alphabet. Each arrow is labelled input/output: the symbol that causes the transition, then the symbol it outputs. There are no accepting states. A Mealy machine is not deciding yes or no; it is translating a string of inputs into a string of outputs of the same length.

Here is a machine for a bump sensor that reads 1 while the bumper is pressed. The robot should react once per bump, not on every tick the bumper stays pressed, so the machine outputs 1 only on a rising edge: the tick where the input changes from 0 to 1.

LOW means "the last input was 0" and HIGH means "the last input was 1". The only transition that outputs 1 is LOW to HIGH.

Tracing a Mealy machine

A trace now records the output of every step as well as the state. Starting in LOW with the input 0110111:

The output is 0100100: two bumps, each reported exactly once. Seven inputs give seven outputs.

In Python, each value in the table becomes a pair: the next state and the output.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

table = {
    ("LOW", "0"): ("LOW", "0"),
    ("LOW", "1"): ("HIGH", "1"),
    ("HIGH", "0"): ("LOW", "0"),
    ("HIGH", "1"): ("HIGH", "0"),
}

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

print(translate("0110111"))

Run this in the simulator

state, out = table[...] unpacks the pair, so the state and the output are updated together, exactly as one transition does both.

Mealy and Moore

There is a second kind of machine with output, the Moore machine, where the output belongs to the state rather than to the transition: every time the machine is in a state it outputs that state's symbol. Anything one can do, the other can too, although a Moore machine may need more states. For AQA you only need Mealy machines, and a question that says "FSM with output" means one.

A robot controller as a Mealy machine

A robot's behaviour is a Mealy machine running forever. Each tick, the sensors are turned into one input symbol, the machine takes one transition, and the output is the action for that tick. For a robot that must find a marker, drive up to it and stop, the input alphabet is:

• none: the marker is not in view;
• far: the marker is in view and more than 15 cm away;
• near: the marker is in view and 15 cm away or less.

The output alphabet is spin, drive and halt.

The table makes you face the awkward cases. What if the marker drops out of view while approaching? The row (APPROACH, none) answers that: go back to searching. With the act in the task below, this never happens in the simulator, because the robot turns towards the marker and keeps it in view all the way in. A real robot is not so lucky: a bump can knock it off line, glare can hide the tag for a few frames, or another robot can pass in front. A bug does it too. Once your task passes, change steer * 3 to steer * -1 in act so the robot turns away from the marker. It loses the marker 18 times, and each time the (APPROACH, none) row sends it back to SEARCH, so it still stops, at 15.3 s instead of 4.2 s. Leave that row out and the program crashes with KeyError: ('APPROACH', 'none') the first time the marker is lost. A hand-written chain of if statements often forgets a case like this; a table with one row for every state and input cannot.

STOP has no transitions out: when the machine reaches it, the run is over. On the real robot, this is the design you would draw before writing any code, and the table is what you would show a teammate to check.

Task: search, approach, stop

Marker 4 is somewhere on the mat, out of view. Run the controller above as a table-driven Mealy machine so the robot finds it, drives up and stops.

• sense() is written for you. It returns a pair: the input symbol ("none", "far" or "near") and a steering value in degrees that act uses.
• act(output, steer) is written for you. It carries out one output symbol ("spin", "drive" or "halt").
• Write table as a dictionary: each key is (state, input) and each value is (next_state, output), with all six rows from the table above.
• Start in "SEARCH". Each tick: sense, look up the transition, act on the output, move to the next state, then wait(0.1). Stop looping when the state is "STOP".
• Whenever the state changes, print the old and new state in the form SEARCH -> APPROACH.

The robot must stop within 20 cm of the marker.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def bearing_of(cx):
    return (cx - 160) * 120 / 320      # pixels to degrees

def sense():
    tags = [t for t in apriltags() if t[0] == 4]
    if not tags:
        return "none", 0
    if tags[0][3] <= 15:
        return "near", 0
    return "far", bearing_of(tags[0][1])

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

set_cv("apriltag")
table = {}
state = "SEARCH"

Challenges

1. Add an input symbol bumped and a state BACK_OFF that reverses for a moment. Write the new rows of the table first.
2. Draw a Mealy machine that outputs 1 on a falling edge, when the bumper is released.
3. Rewrite the edge detector as a Moore machine. How many states does it need?