Constructing and Testing Finite State Machines

AQA 4.4.12 — Constructing finite state machines

Retrieval: the previous lesson traced existing FSMs. This lesson builds new ones from a written requirement, using the exact same state-meanings-first discipline that lesson modelled.

Understand — the construction method

1. Identify what needs remembering. Read the specification and work out exactly what information about "the input so far" actually determines the correct next action — this becomes your set of states.
2. Define each state's meaning in words first, before assigning any labels or working out a single transition. A state without a precise, written meaning is where construction errors creep in.
3. Work out transitions systematically, one state at a time, asking "given this state's meaning, what does each possible input symbol do to that meaning?"
4. Identify accepting states — whichever state-meanings correspond to the specification actually being satisfied.
5. Check completeness — every state needs a transition defined for every symbol in the alphabet.

See it — constructing "at least one 1"

Specification: accept any binary string containing at least one 1.

State meanings: q0 (start) — no 1 has been seen yet. q1 (accepting) — at least one 1 has been seen.

Once q1 is reached, every further symbol keeps the machine in q1 — a "sink" accepting state, since once at least one 1 has appeared, that fact can never become untrue.

See it — a richer, real-life example: login lockout

Specification: a login system locks an account after 3 consecutive incorrect password attempts; a correct attempt at any point logs the user in.

State meanings: Attempt1 (start) — no failed attempts yet. Attempt2 — exactly 1 consecutive failed attempt. Attempt3 — exactly 2 consecutive failed attempts. LoggedIn (accepting) — password entered correctly. Locked (accepting) — 3 consecutive failures reached.

This FSM has two accepting states representing two genuinely different outcomes — acceptance doesn't have to mean just one thing.

Test it — systematically checking valid and invalid cases

Deliberately testing both a string that should reach each accepting state, and a string that recovers partway through, is what genuinely tests an FSM's construction — not just one "happy path" example.

Debug it — diagnose, explain, fix, test, justify (accepts an invalid string)

A student constructs the "at least one 1" FSM above but mistakenly marks q0 as accepting too:

1. Diagnose: does q0's actual meaning ("no 1 seen yet") genuinely satisfy the specification ("contains at least one 1")?
2. Explain: what string would this flawed FSM incorrectly accept, that shouldn't be accepted?
3. Fix: correct the accepting-state definition.
4. Test: confirm "000" is now correctly rejected, while "001" remains correctly accepted.
5. Justify: explain why marking the start state as accepting is a particularly easy mistake to make, and why checking each state's own written meaning against the specification (not just guessing) prevents it.

(q0 means "no 1 seen yet" - the exact OPPOSITE of what the specification requires, so marking it accepting is wrong. The flawed FSM would incorrectly accept "000" (and even the empty string), which contain no 1s at all. The fix removes q0 from the accepting states, leaving only q1. This mistake is easy to make because the start state is often written first, before the state-meanings-first discipline has been fully applied - checking q0's own definition against the specification directly (rather than assuming a start state is never accepting, which isn't a real rule) is what catches it.)

Debug it — diagnose, explain, fix, test, justify (missing a necessary transition)

A student builds the login-lockout FSM above but forgets to define what happens on wrong while in Attempt3:

1. Diagnose: does every state in this table have a transition defined for every symbol in the alphabet?
2. Explain: what happens when the sequence wrong, wrong, wrong is processed and the machine reaches Attempt3, then reads another wrong?
3. Fix: add the missing transition.
4. Test: confirm wrong, wrong, wrong now correctly reaches Locked.
5. Justify: explain why an incomplete transition table is a genuine construction error, not simply an unfinished detail.

(Attempt3 has no transition defined for "wrong", so the FSM is incomplete. Processing a third consecutive "wrong" leaves the machine with no defined next state at all - genuinely undefined behaviour, not merely a missing feature. The fix adds Attempt3, wrong -> Locked. A deterministic FSM is only well-defined if literally every state-symbol pair has a transition - an omission here means the model itself is incomplete, not just missing an edge case someone forgot to code.)

Common mistake

Assuming an FSM's states can be figured out purely by "counting things that happened" without first writing down what each count actually means for the specification. The login example's states aren't just "1 failure, 2 failures, 3 failures" — they're specifically "number of consecutive failures," a distinction that matters enormously (a correct attempt resets the count, it doesn't just add to it).

Why this matters for the NEA

Modelling a program's own possible states — which screen is showing, whether a user is logged in, what mode an editor is in — using exactly this states-and-transitions discipline is a genuine, useful design tool for planning an NEA project's interface logic, distinct from writing the NEA's actual code.

Check your understanding

Construct an FSM (state meanings, then a full transition table) that accepts binary strings of even length (including the empty string, length 0). (4 marks)

(State meanings: E (start, accepting) - even number of symbols read so far; O - odd number of symbols read so far. Table: E on 0 -> O; E on 1 -> O; O on 0 -> E; O on 1 -> E. E is accepting (0, 2, 4... symbols read); O is not.)

Challenge

Construct an FSM for: "accepts strings over {a, b} that contain the substring aa anywhere." Define your state meanings precisely before building the transition table, then test it against at least one string that should be accepted and one that should be rejected.

Looking ahead: the next lesson steps back from FSMs to the mathematical foundations — sets, alphabets and languages — that regular expression notation is directly built from.