Finite State Machines (FSMs)

A Finite State Machine (FSM), also called a finite automaton, is a mathematical model of computation with a finite number of states. At any instant the machine is in exactly one state; it moves between states in response to inputs according to a fixed set of transition rules. FSMs are deceptively simple yet enormously useful: they model everything from a vending machine to the lexical analyser inside a compiler. They are also the gateway to the deeper theory of computation, because the languages they can recognise — the regular languages — form the base of the Chomsky hierarchy. The AQA specification expects you to handle FSMs both with and without output, to read and write transition diagrams and tables, and to trace specific strings to decide acceptance.

---

Spec Mapping

This lesson addresses the Theory of Computation strand (around section 4.4.2) of AQA A-Level Computer Science (7517). You are expected to understand FSMs both without output (acceptors that decide whether a string belongs to a language, using accepting/final states) and with output (transducers — specifically Mealy and Moore machines). You must be able to draw and interpret state transition diagrams, construct and read state transition tables, identify the start state and accepting states, and trace the processing of a given input string to determine whether it is accepted or rejected. The descriptions here are in the standard automata-theory vocabulary; learn the concepts, not any verbatim phrasing.

---

Formal Definition

A finite state machine that acts as an acceptor is defined as a 5-tuple $(Q, \Sigma, \delta, q_0, F)$(Q,Σ,δ,q0​,F):

Symbol	Meaning
$Q$Q	A finite set of states
$\Sigma$Σ (sigma)	A finite set of input symbols — the alphabet
$\delta$δ (delta)	A transition function $\delta(\text{state}, \text{input}) \rightarrow \text{next state}$δ(state,input)→next state
$q_0$q0​	The start state, $q_0 \in Q$q0​∈Q
$F$F	The set of accepting (final) states, $F \subseteq Q$F⊆Q

A string is accepted if, starting from $q_0$q0​ and consuming every symbol in turn, the machine ends in a state that belongs to $F$F. Otherwise the string is rejected. Note carefully: only the final state matters — passing through an accepting state mid-string is irrelevant.

---

Deterministic vs Non-Deterministic FSMs

	Deterministic (DFA)	Non-deterministic (NFA)
Transitions per (state, symbol)	Exactly one	Zero, one, or many
Empty (ε) moves allowed?	No	Yes
Behaviour	Single defined path	Conceptually explores all paths at once; accepts if any path ends in $F$F

The crucial theoretical fact is that this difference makes no difference to expressive power: every NFA can be converted to an equivalent DFA (the subset construction), so both recognise exactly the regular languages. Non-determinism is a convenience for design, not extra power. At A-Level you will mostly draw deterministic machines.

---

State Transition Diagrams

The standard visual notation:

• states are circles;
• transitions are arrows labelled with the input symbol that triggers them;
• the start state has an incoming arrow from nowhere;
• accepting states are drawn as double circles.

Worked FSM: strings over {0, 1} that end in "01"

stateDiagram-v2
    [*] --> S0
    S0 --> S1 : 0
    S0 --> S0 : 1
    S1 --> S1 : 0
    S1 --> S2 : 1
    S2 --> S1 : 0
    S2 --> S0 : 1
    S2 --> [*]

Read the states as memory of how far through the pattern "01" we are: S0 = "have not just seen the start of the pattern"; S1 = "the last symbol was a 0 (a possible start of 01)"; S2 = "the last two symbols were 01" — the accepting state.

• States: {S0, S1, S2}; start: S0; accepting: {S2}.

Acceptance trace — "1001" (should be accepted)

Step	Current state	Input read	Next state
1	S0	1	S0
2	S0	0	S1
3	S1	0	S1
4	S1	1	S2

The machine ends in S2, which is accepting, so "1001" is accepted (it does end in "01").

Rejection trace — "1010" (should be rejected)

Step	Current state	Input read	Next state
1	S0	1	S0
2	S0	0	S1
3	S1	1	S2
4	S2	0	S1

The machine passes through S2 at step 3 but ends in S1, which is not accepting, so "1010" is rejected (it ends in "10"). This illustrates why only the final state counts.

---

State Transition Tables

The same machine written as a transition table — often easier to work with than a diagram, and frequently what exams ask you to complete:

Current state	Input 0	Input 1
→ S0	S1	S0
S1	S1	S2
* S2	S1	S0

The arrow (→) marks the start state and the asterisk (*) marks an accepting state. A diagram and a table carry identical information; you should be able to convert freely between them. A common exam task gives you one representation and asks for the other, or gives you a table and a string to trace.

---

A Second Worked Acceptor: Binary Numbers Divisible by 3

This is a favourite exam machine because it shows how cleverly chosen states encode arithmetic. We want an FSM that accepts a binary string exactly when the number it represents is divisible by 3. The trick is that each state will remember the remainder of the number-so-far when divided by 3 — and there are only three possible remainders (0, 1, 2), so three states suffice.

Reading binary left to right, appending a bit b to a number n gives 2n + b. So if the current remainder is r, the new remainder is (2r + b) mod 3. Working that out for every case gives the transition table:

Current state (remainder)	Input 0 →	Input 1 →	Reasoning
→ * R0 (rem 0)	R0	R1	2·0+0=0; 2·0+1=1
R1 (rem 1)	R2	R0	2·1+0=2; 2·1+1=3≡0
R2 (rem 2)	R1	R2	2·2+0=4≡1; 2·2+1=5≡2

R0 is both the start state (an empty/zero value has remainder 0) and the only accepting state.

stateDiagram-v2
    [*] --> R0
    R0 --> R0 : 0
    R0 --> R1 : 1
    R1 --> R2 : 0
    R1 --> R0 : 1
    R2 --> R1 : 0
    R2 --> R2 : 1
    R0 --> [*]

Trace — "110" (which is 6 in decimal, and 6 is divisible by 3):

Step	Current state	Input	Next state	Number so far
1	R0	1	R1	1 (rem 1)
2	R1	1	R0	3 (rem 0)
3	R0	0	R0	6 (rem 0)

Ends in R0 (accepting) → accepted. ✓ (6 ÷ 3 = 2.)

Trace — "1011" (which is 11, not divisible by 3):

Step	Current state	Input	Next state	Number so far
1	R0	1	R1	1 (rem 1)
2	R1	0	R2	2 (rem 2)
3	R2	1	R2	5 (rem 2)
4	R2	1	R2	11 (rem 2)

Ends in R2 (not accepting) → rejected. ✓ (11 = 3·3 + 2.) This example is the clearest demonstration of the central FSM idea: the states are the machine's entire memory, and three remainders need exactly three states. A "divisible by 5" version would need five states, "divisible by k" needs k states — always finite, which is precisely why divisibility is a regular property.

One further idea this example brings out is that different FSMs can recognise the same language. We could pointlessly add a fourth state that behaves identically to R0; the resulting machine would accept exactly the same strings but with one redundant state. The version with the fewest states is called the minimal machine, and there is a systematic procedure (state minimisation) for merging states that can never be told apart by any future input. For exam purposes the lesson is simply this: when you design an FSM, aim for the smallest set of states that captures the necessary distinctions — three remainders, two parities, one suffix-progress counter — and resist adding states that duplicate behaviour you already have.

---

FSMs with Output: Mealy and Moore Machines

The acceptors above only ever answer "accept" or "reject". An FSM with output (a transducer) emits an output symbol as it runs. There are two standard kinds, and distinguishing them is a favourite exam discriminator.

Moore machine — output depends on the state

In a Moore machine each state is labelled with a fixed output, produced whenever the machine is in that state. Output therefore changes only when the state changes, one step after the input that caused the change.

stateDiagram-v2
    [*] --> A
    A : A / out=0
    B : B / out=1
    A --> B : 1
    A --> A : 0
    B --> A : 0
    B --> B : 1

This Moore machine outputs 1 exactly when the most recent input has driven it into state B (here, tracking an "odd number of 1s so far" condition).

Mealy machine — output depends on state and input

In a Mealy machine the output is attached to each transition, so it depends on both the current state and the symbol being read. Output appears in the same step as the triggering input.

stateDiagram-v2
    [*] --> P
    P --> Q : 1 / 1
    P --> P : 0 / 0
    Q --> P : 0 / 0
    Q --> Q : 1 / 0

The transition labels read input / output. This Mealy machine outputs a 1 on the transition that first sees a 1 after a 0 — a simple rising-edge detector.

Comparison

Feature	Moore machine	Mealy machine
Output is a function of	The current state only	The current state and the input
Output appears	On entering a state (one step after the input)	On the transition (in the same step as the input)
Output labelling	On states	On transitions
States needed	Often more	Often fewer

A useful rule of thumb: Moore depends on the state (one input, delayed output); Mealy reacts immediately to the input on the edge. They can compute the same input-output relationships, but Mealy machines typically need fewer states because they can act on the input directly rather than first changing state.

Worked Output Trace: a Vending-Machine Transducer

To make the Mealy/Moore distinction concrete, consider a simplified drinks machine. A can costs 30p and accepts only 10p and 20p coins; when enough money has been inserted it outputs dispense, otherwise wait (for simplicity assume exact change, so 10p+20p or 20p+10p or 10p+10p+10p reaches 30p). The natural design is a Mealy machine, because the dispense action is triggered by the coin that completes the payment — i.e. it depends on both the current total (the state) and the coin just inserted (the input).

States track the money inserted so far: S0 (0p, start), S10 (10p), S20 (20p). Transitions are labelled coin / output:

stateDiagram-v2
    [*] --> S0
    S0 --> S10 : 10 / wait
    S0 --> S20 : 20 / wait
    S10 --> S20 : 10 / wait
    S10 --> S0 : 20 / dispense
    S20 --> S0 : 10 / dispense

Trace — inserting 20p then 10p:

Step	Current state	Coin in	Output	Next state
1	S0	20	wait	S20
2	S20	10	dispense	S0

The dispense output appears on the transition that reaches 30p — it depends on being in state S20 and receiving a 10p coin. A Moore version would need an extra dedicated "30p reached" state whose label is dispense, because in a Moore machine the output belongs to a state, not a transition. This is the classic illustration of why Mealy machines often need fewer states: the Mealy machine reacts to the completing coin directly, whereas the Moore machine must first move into a special state and only then emit the output. Both are correct; the choice is about which is the more natural and economical fit.

---

What Can — and Cannot — Be Recognised

An FSM has no memory beyond its current state. With a fixed, finite number of states it can "remember" only a bounded amount of information. This is precisely why it recognises the regular languages and nothing more.

Pattern	FSM can recognise?	Why
Strings ending in "01"	Yes	Three states suffice to track progress through the pattern
Strings with an even number of 1s	Yes	Two states (even / odd) track parity
Binary numbers divisible by 3	Yes	Three states track the remainder mod 3
Balanced brackets, e.g. ((()))	No	Nesting depth is unbounded; needs a stack (a pushdown automaton)
Strings of the form $a^n b^n$anbn	No	Requires counting the as and matching them with the bs — unbounded memory