Finite state machines

States, transitions and accepting states; state transition diagrams and tables; tracing an FSM and running one from a table.

A6.1Theory of computationA level20 min

In robotics lesson 5.2 you gave a robot a plan by keeping a state variable and changing it when something happened. Theory of computation takes that idea and makes it exact. A finite state machine (FSM) is the simplest model of a computer there is: it has no variables and no memory apart from which state it is in. This module climbs from FSMs to regular expressions, grammars and finally the Turing machine, and asks a question GCSE never did: what can a computer do at all?

What an FSM is

A finite state machine has:

• a finite set of states, such as S0 and S1;
• an input alphabet: the symbols it can read, such as 0 and 1;
• a start state, where every run begins;
• a transition function: for each state and input symbol, the state to move to next;
• for a machine with no output, a set of accepting states (also called goal or final states).

The machine reads its input one symbol at a time, left to right, and follows one transition per symbol. When the input runs out, it accepts the input if it is in an accepting state and rejects it otherwise. An FSM used this way is a recogniser: it sorts every possible input string into yes or no.

State transition diagrams

In a state transition diagram each state is a circle and each transition is an arrow labelled with the input symbol that causes it. The start state has an arrow coming in from nowhere, and an accepting state is drawn with a double circle.

This machine accepts binary strings with an even number of 1s. S0 means "an even number of 1s so far" and S1 means "odd so far". A 0 changes nothing, so it loops back to the same state. A 1 swaps between the two. S0 is both the start state and the only accepting state, because before reading anything the count of 1s is zero, which is even.

Notice what the machine does not do: it never counts. It only remembers whether the count is odd or even, and two states are enough to hold that.

State transition tables

The same machine as a state transition table. There is one row for every pair of state and input:

A diagram and a table hold exactly the same information, and exam questions ask you to turn one into the other. Check a table has a row for every state with every symbol: two states and two symbols make four rows.

Tracing a run

To trace the input 1011, write down each state in turn:

The input ends in S1, which is not accepting, so 1011 is rejected. It has three 1s, which is odd, so that is right.

An FSM in Python

The transition function is a lookup from a pair (state, symbol) to the next state, so a dictionary with tuple keys stores the table directly. The program that runs the machine never changes; only the table does.

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

table = {
    ("S0", "0"): "S0",
    ("S0", "1"): "S1",
    ("S1", "0"): "S1",
    ("S1", "1"): "S0",
}
start = "S0"
accepting = {"S0"}

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

for text in ["1011", "1001", "0", "111"]:
    print(text, accepts(text))

Run this in the simulator

This prints False for 1011 and 111 (three 1s each) and True for 1001 and 0. The same loop in the style of AQA's pseudo-code:

state ← "S0"
FOR i ← 0 TO LEN(text) - 1
  state ← table[state, text[i]]
ENDFOR
IF state = "S0" THEN
  OUTPUT "accept"
ELSE
  OUTPUT "reject"
ENDIF

Missing transitions and trap states

Some diagrams leave out transitions. A machine that accepts binary strings starting with 1 might show only S0 going to S1 on a 1, and S1 looping on 0 and 1. What happens on a 0 in S0? By convention a missing transition means the input is rejected at once. To make the table complete, add a trap state (sometimes called a dead state): a non-accepting state that every symbol loops back to. Once the machine falls in, nothing can get it out.

Where FSMs are used

FSMs are everywhere a system has a small number of modes: traffic lights, lifts, vending machines, network protocols, the menus of a washing machine, and the behaviour of a robot. In a compiler, the lexical analyser that splits source code into tokens is an FSM. Designing with states forces you to decide, for every mode, what every input does, which is exactly the thinking that stops a robot behaving strangely in a case nobody considered.

Task: ends in 01

Design a finite state machine that accepts binary strings that end in 01, store it as a transition table, and run it.

• table is a dictionary: each key is a pair (state, symbol), where symbol is the string "0" or "1", and each value is the next state. Include a transition for every state with both symbols.
• The machine must decide by following transitions one symbol at a time. Do not look at the end of the string directly.
• For each string in tests, in order, print one line: the string, a space, then accept or reject. For example 1101 accept. Six lines in all.

Work out what each state needs to remember before you write the table: how much of 01 has the machine just seen?

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

tests = ["01", "1101", "0110", "1", "00101", "0100"]

table = {}

Challenges

1. Draw the state transition diagram for your machine. Which state is accepting?
2. Change your table so it accepts strings that contain 00 anywhere. Does it need a trap state, or a state it can never leave?
3. What does the parity machine do with the empty string? Why is that the right answer?