Finite State Machines: States, Transitions and Tracing

AQA 4.4.12 — Finite state machines

Retrieval: Sequence 14's abstraction-information-hiding established that a valid abstraction deliberately discards irrelevant detail while keeping exactly what a purpose needs. A Finite State Machine (FSM) is precisely this kind of abstraction, applied to modelling a system's behaviour over time: it deliberately reduces an entire system down to a fixed number of states and the transitions between them, discarding everything else about how the system actually works internally.

Key vocabulary

• State — one specific "mode" or "situation" the system can be in at a given moment.
• Alphabet — the finite set of valid input symbols the machine can receive.
• Transition — a rule: being in a specific state, and receiving a specific input symbol, moves the machine to a specific next state.
• Start state — the one state the machine begins in before any input is processed.
• Accepting (final) state — a state that, if the machine is in it once the entire input string has been processed, means the machine accepts that string.
• Deterministic — for every state and every symbol in the alphabet, there is exactly one defined next state (no ambiguity, no choice).

Understand — what an FSM formally consists of

A (deterministic) finite state machine is fully defined by exactly five things: a finite set of states; a finite alphabet of input symbols; a transition rule covering every state–symbol combination; one designated start state; and a set of accepting states (which may be empty, one, or several). Nothing else is part of the model — this is the deliberate abstraction Sequence 14 introduced: an FSM throws away how a real system works internally and keeps only which situation it's in and what causes it to change situation.

See it — a turnstile

A real turnstile has exactly two meaningful states for our purposes: Locked and Unlocked. The alphabet is {coin, push}.

              coin
      ┌────────────────────┐
      ▼                    │
──▶ (Locked)            (Unlocked)
      │                    ▲
      └────────────────────┘
              push
   (Locked --push--> Locked is a self-loop,
    not shown, to keep the diagram readable —
    see the table above for the complete definition)

This turnstile FSM has no accepting states at all — it's used purely to track which state the system is in, not to accept or reject a whole sequence of inputs.

See it — a genuine string-recognising FSM

Specification: accept any binary string (over {0, 1}) that ends in "01".

State meanings, defined precisely before working out any transitions — this is the key construction discipline the next lesson builds on:

• q0 (start) — the string read so far does not end in 0 (either it's empty, or its last character is 1).
• q1 — the string read so far ends in 0.
• q2 (accepting) — the string read so far ends in 01.

      input: 0                input: 1
──▶ (q0) ─────────────▶ (q1) ─────────────▶ ((q2))
      ▲                                        │
      └──────────── input: 1 ─────────────────┘
   (self-loops q1--0-->q1 and q2--0-->q1 are omitted
    here for readability — see the full table above)

Trace it — accepting a string

Tracing "1001" symbol by symbol:

After all 4 symbols, the machine is in q2, an accepting state — "1001" is accepted. Checking by eye: "1001" genuinely ends in "01". ✓

Trace it — rejecting a string

Tracing "1010": q0 →(1)→ q0 →(0)→ q1 →(1)→ q2 →(0)→ q1. After all 4 symbols, the machine is in q1, not an accepting state — "1010" is rejected. Checking by eye: "1010" ends in "10", not "01". ✓

Explain acceptance and rejection, precisely

A string is accepted if, after the machine has consumed every single symbol of the string (not just some prefix of it), the machine is in an accepting state. It is rejected if, after consuming the entire string, the machine is in a non-accepting state. A common misunderstanding is thinking the machine "stops as soon as it reaches" an accepting state mid-string — it doesn't; it keeps processing every remaining symbol, and only the final state (after the whole string) determines acceptance, exactly why "1001" passing briefly through q2 partway (if it did) wouldn't matter unless q2 is also where it ends up.

Common mistake

Assuming a deterministic FSM can simply have "no transition defined" for some state–symbol pair, and that the machine just "stops" there. A properly constructed deterministic FSM must have a transition defined for every state–symbol combination — an "undefined" transition is a genuine construction error (the next lesson's Debug it task covers exactly this).

Identify it

For the "ends in 01" FSM above, identify: (a) the alphabet; (b) the start state; (c) the accepting state(s); (d) what happens on input 1 while in state q1.

(a: {0, 1}. b: q0. c: q2 only. d: transitions to q2, since reading a 1 while the string so far ends in 0 means the string now ends in "01".)

Real-life applications

• Traffic light controller — states Red, Red-Amber, Green, Amber, cycling in a fixed, predictable order regardless of how long each state lasts.
• Login/lockout system — states tracking the number of consecutive failed password attempts, moving to a Locked state after a fixed number of failures (the next lesson builds this exact example in full).
• Vending machine — states tracking how much credit has been inserted, moving to a "dispense" state once enough coins have been received.

Check your understanding

A simple FSM over the alphabet {a, b} has states p0 (start), p1 (accepting). Transitions: p0 on a → p1; p0 on b → p0; p1 on a → p1; p1 on b → p0. Trace the string "bab" and state whether it is accepted or rejected, showing your working. (3 marks)

(p0 --b--> p0 --a--> p1 --b--> p0. Final state p0, not accepting - rejected. Working: start p0; read 'b', stay p0; read 'a', move to p1; read 'b', move back to p0.)

Challenge

This FSM's accepting state p1 is reached exactly when the string read so far ends in a. Describe, in words, the complete language this FSM accepts (every possible string satisfying this).

Looking ahead: the next lesson uses this exact state-meanings-first discipline to construct an FSM from a written specification, then systematically tests it against valid and invalid strings.