Finite State Machines and Regular Expressions

Finite state machines

A finite state machine (FSM) is a model of something that is always in exactly one state out of a fixed, finite list. It reads an input, and the current state plus that input decide the next state. Nothing else is remembered.

Many things work this way: a turnstile is locked or unlocked, a traffic light is red, red and amber, green or amber, a game enemy is patrolling, chasing or fleeing.

An FSM is described by:

• a set of states
• one start state
• the inputs it can read
• the transitions: for each state and input, the next state

A state transition diagram shows states as circles and transitions as labelled arrows. The same information fits in a state transition table, which is easy to put straight into code as a dictionary.

transitions = {
    ("locked", "coin"): "unlocked",
    ("locked", "push"): "locked",
    ("unlocked", "coin"): "unlocked",
    ("unlocked", "push"): "locked",
}

state = "locked"
for event in ["push", "coin", "coin", "push", "push"]:
    state = transitions[(state, event)]
    print(event, "->", state)

The whole behaviour of the turnstile is in that table. There are no if statements deciding what to do: the machine is data, and one short loop runs any machine you give it.

Machines that accept or reject

An acceptor has a set of accepting states, drawn with a double circle. It reads a whole string. If it finishes in an accepting state it accepts the string, otherwise it rejects it. The set of every string a machine accepts is its language.

This machine accepts binary strings that contain an even number of 1s. It has two states, because all it needs to remember is whether it has seen an even or an odd number so far.

def accepts(machine, text):
    state = machine["start"]
    for symbol in text:
        if (state, symbol) not in machine["table"]:
            return False                        # no transition: the string is rejected
        state = machine["table"][(state, symbol)]
    return state in machine["accepting"]

even_ones = {
    "start": "even",
    "accepting": {"even"},
    "table": {("even", "0"): "even", ("even", "1"): "odd",
              ("odd", "0"): "odd", ("odd", "1"): "even"},
}

for text in ["", "0", "1", "11", "1011", "10101"]:
    print(repr(text), accepts(even_ones, text))

If a state has no transition for an input, the machine rejects. Drawings usually leave out this dead state (a state that can never lead back to acceptance) to keep the diagram readable.

A surprising machine: is a binary number divisible by 3?

Read a binary number one bit at a time, from the left. Keep only its remainder when divided by 3. Reading another bit doubles the number and adds the bit, so the new remainder is (2 * r + bit) % 3. Three possible remainders means three states, and that is all the memory needed to test a number of any length.

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

def divisible_by_3():
    table = {}
    for remainder in range(3):
        for bit in "01":
            table[(remainder, bit)] = (2 * remainder + int(bit)) % 3
    return {"start": 0, "accepting": {0}, "table": table}

machine = divisible_by_3()
wrong = [n for n in range(200) if accepts(machine, bin(n)[2:]) != (n % 3 == 0)]
print("numbers the machine got wrong:", wrong)
print("transitions:", len(machine["table"]))
print(accepts(machine, "1100"), accepts(machine, "1101"))     # 12 and 13

Machines with output: Mealy machines

An acceptor only answers yes or no. A Mealy machine also writes an output on every transition, so it can transform its input. This one adds 1 to a binary number. It reads the bits starting from the least significant end, as a column addition does, and carries as it goes.

RULES = {
    ("carry", "0"): ("done", "1"),      # 0 plus the carry is 1, and the carry is used up
    ("carry", "1"): ("carry", "0"),     # 1 plus the carry is 0, and the carry moves on
    ("done", "0"): ("done", "0"),       # nothing left to add: copy the bit
    ("done", "1"): ("done", "1"),
}

def add_one(bits_lsb_first):
    state, out = "carry", []
    for bit in bits_lsb_first:
        state, written = RULES[(state, bit)]
        out.append(written)
    if state == "carry":
        out.append("1")                 # the carry ran off the end
    return "".join(out)

for n in [5, 6, 7]:
    lsb = bin(n)[2:][::-1]
    result = add_one(lsb)
    print(n, "->", int(result[::-1], 2))

On a transition diagram a Mealy machine's arrows are labelled input / output.

Regular expressions

A regular expression (regex) is a compact way of writing a set of strings. Instead of listing them, you describe their pattern. There are only three building blocks, and everything else is shorthand for them:

The shorthand most worth knowing:

Python's re module runs them. The key question is how much of the text must match:

import re

print(re.fullmatch(r"\d+", "12abc"))             # None: the whole string must match
print(re.match(r"\d+", "12abc") is not None)     # True: matches at the start only
print(re.search(r"\d+", "ab12c").group())        # 12: finds it anywhere
print(re.findall(r"\b[A-Z][a-z]+\b", "Alice met Bob in Paris"))
print(re.sub(r"\s+", " ", "too    many   spaces"))

An acceptor decides whether the whole string is in its language, so re.fullmatch is the Python equivalent.

Patterns that validate

import re

plate = re.compile(r"[A-Z]{2}[0-9]{2} [A-Z]{3}")        # a current UK number plate
clock = re.compile(r"([01][0-9]|2[0-3]):[0-5][0-9]")    # a 24 hour time

for text in ["AB12 CDE", "ab12 cde", "AB12CDE", "XY99 ZZZ"]:
    print(text, bool(plate.fullmatch(text)))
for text in ["09:30", "23:59", "24:00", "7:05", "12:60"]:
    print(text, bool(clock.fullmatch(text)))

Two traps

import re

print(re.findall("a.c", "abc a.c"))        # the dot matches any character
print(re.findall(r"a\.c", "abc a.c"))      # \. matches only a real full stop

html = "<b>bold</b> and <i>it</i>"
print(re.findall(r"<.+>", html))           # greedy: takes as much as it can
print(re.findall(r"<.+?>", html))          # lazy: takes as little as it can

Two descriptions of the same languages

Regular expressions and finite state machines look like different tools: one is written text, the other a diagram. In fact, they describe exactly the same sets of strings. Any language you can write as a regular expression, some FSM accepts, and the other way round. These are called the regular languages.

You can test the claim. The regular expression (0|10*1)* says: any number of repeats of either a lone 0, or a 1, then any 0s, then another 1. Each repeat uses 1s in pairs, so it should match exactly the strings with an even number of 1s: the language of the first machine in this topic. Try every binary string up to length 8:

import re
from itertools import product

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

even_ones = {
    "start": "even",
    "accepting": {"even"},
    "table": {("even", "0"): "even", ("even", "1"): "odd",
              ("odd", "0"): "odd", ("odd", "1"): "even"},
}
pattern = re.compile(r"(0|10*1)*")

disagree = []
tested = 0
for length in range(9):
    for chars in product("01", repeat=length):
        text = "".join(chars)
        tested += 1
        if (pattern.fullmatch(text) is not None) != accepts(even_ones, text):
            disagree.append(text)

print(tested, "strings tested;", len(disagree), "disagreements")

A second pair: the regex (ab)*c is ab repeated any number of times, then a c. Draw it as a machine: from the start, a leads to a state that expects b, and b leads back to the start. A c from the start reaches the only accepting state.

import re
from itertools import product

machine = {
    "start": "S0",
    "accepting": {"S2"},
    "table": {("S0", "a"): "S1", ("S1", "b"): "S0", ("S0", "c"): "S2"},
}

def accepts(machine, text):
    state = machine["start"]
    for symbol in text:
        if (state, symbol) not in machine["table"]:
            return False
        state = machine["table"][(state, symbol)]
    return state in machine["accepting"]

pattern = re.compile(r"(ab)*c")
tested = 0
different = []
for length in range(7):
    for chars in product("abc", repeat=length):
        text = "".join(chars)
        tested += 1
        if (pattern.fullmatch(text) is not None) != accepts(machine, text):
            different.append(text)
print(tested, "strings tested;", len(different), "disagreements")

This is more than a curiosity. When you compile a regular expression, the engine builds a state machine from it and runs the input through that machine. The first stage of a compiler, which splits source code into words, is built the same way, as the next topic shows.

What a finite state machine cannot do

Because an FSM has only a fixed number of states, it cannot count without a limit. Take a simple task: decide whether a string of brackets is balanced, meaning every ( is closed by a matching ). (())() is balanced. (() and ())( are not.

To check it you must remember how deeply nested you are. That depth could be 5, or 500, or 5 million. A machine with a fixed number of states can only count up to a fixed depth.

Here is a machine built for a maximum depth. Its state is the current depth:

def make_machine(max_depth):
    table = {}
    for depth in range(max_depth + 1):
        if depth < max_depth:
            table[(depth, "(")] = depth + 1
        if depth > 0:
            table[(depth, ")")] = depth - 1
    return {"start": 0, "accepting": {0}, "table": table}

def accepts(machine, text):
    state = machine["start"]
    for symbol in text:
        if (state, symbol) not in machine["table"]:
            return False
        state = machine["table"][(state, symbol)]
    return state in machine["accepting"]

def balanced(text):
    depth = 0
    for symbol in text:
        depth += 1 if symbol == "(" else -1
        if depth < 0:
            return False
    return depth == 0

deep = "((((" + "))))"
for limit in (2, 3, 5):
    machine = make_machine(limit)
    print("depth limit", limit, ":", accepts(machine, "(())"), accepts(machine, deep), "| really balanced:", balanced(deep))

The machine with a limit of 2 wrongly rejects a perfectly good string of depth 4, and the machine with a limit of 3 does too. Raising the limit helps, but whatever limit you pick, there is a deeper string to defeat it. The function balanced has no such limit because the variable depth is a number that can grow, which is unbounded memory.

The extra memory that bracket matching needs behaves like a stack: push on (, pop on ). A machine with a stack is more powerful than an FSM. It can recognise languages such as the balanced brackets or aaabbb (n letter as followed by n letter bs), which no FSM and no regular expression can. These are described by grammars instead, which is where the next topic starts.

Key terms you must be able to define

Finite state machine

An abstract machine that is in one of a finite number of states, and changes state in response to inputs according to a set of transitions.

State

One of the conditions the machine can be in. It is the machine's only memory.

Transition

A change from one state to another, triggered by an input.

State transition diagram

A drawing of an FSM with circles for states and labelled arrows for transitions.

State transition table

A table giving the next state for every combination of current state and input.

Accepting state

A state, drawn as a double circle, in which finishing means that the input string is accepted.

Mealy machine

A finite state machine that produces an output on each transition, as well as changing state.

Regular expression

A pattern, built from concatenation, alternation and repetition, that describes a set of strings.

Regular language

A set of strings that can be described by a regular expression and accepted by a finite state machine.

Greedy match

A repetition that matches as much text as it can. Adding a question mark makes it lazy.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

FSM questions are about reading and drawing accurately, with a short reason for the limits.

• Trace an input by writing the state after each symbol, and state the final state before you say accepted or rejected
• In a diagram, mark the start state with an arrow, the accepting states with double circles, and label every arrow
• For a Mealy machine, label arrows with input and output, and trace both
• For regular expressions, say what each part does: [0-9]{2} is exactly two digits
• Explain a limit with a cause: finite states, therefore no unbounded counting

Mistakes that cost marks here

current   input   next
S0        0       S0
S0        1       S1
S1        0       S0
S1        1       S2
S2        0       S2
S2        1       S2

import re

clock = re.compile(r"([01][0-9]|2[0-3]):[0-5][0-9]")
print(bool(clock.fullmatch("07:45")), bool(clock.fullmatch("24:00")))