Finite State Machines for GCSE Computer Science: States, Transitions and Diagrams

A finite state machine (FSM) is a computational model with a fixed set of states, one of which is always the current state. The machine transitions between states in response to inputs. FSMs appear in GCSE Computer Science as transition diagrams and are used to model real systems from vending machines to password validators.

What are the key components of a finite state machine?

Every FSM has five components, sometimes written as a 5-tuple:

1. A set of states (S) — the complete list of possible conditions the machine can be in. The number of states is finite (hence the name).
2. An input alphabet (Σ) — the set of all possible inputs the machine can receive (e.g. {0, 1}, or {coin, button}).
3. A transition function (δ) — the rules that say: "given current state X and input Y, move to state Z".
4. An initial (start) state (s₀) — the state the machine begins in, marked with an arrow in transition diagrams.
5. A set of accept (final) states (F) — states that represent a successful or completed condition, shown with a double circle in transition diagrams.

How do you draw a transition diagram?

A transition diagram is the visual representation of an FSM. The conventions are:

• Each state is drawn as a circle, labelled with its name.
• The start state has an arrow pointing to it from nowhere (or a small filled circle).
• Accept/final states are drawn with a double circle.
• Transitions are drawn as labelled arrows between states. The label shows the input that causes that transition.

Worked example — a simple light switch FSM:

This FSM models an on/off toggle switch.

• States: {OFF, ON}
• Input alphabet: {press}
• Start state: OFF
• Accept state: ON

Transition rules:

• In state OFF, input press → move to ON
• In state ON, input press → move to OFF

In a diagram, this is two circles (OFF and ON) with arrows labelled "press" going in both directions. OFF has the entry arrow; ON has the double circle.

How do you represent transitions as a table?

A state transition table captures the same information as a diagram in a grid format:

For more complex FSMs, the table makes it easier to check that every state/input combination is defined.

A more complex worked example: coin-operated turnstile

A turnstile has two states: LOCKED and UNLOCKED.

• Inserting a coin when locked → unlocks it.
• Pushing when unlocked → allows entry and re-locks.
• Pushing when locked → stays locked (no entry).
• Inserting a coin when already unlocked → stays unlocked (excess coin, in a simple model).

Input alphabet: {coin, push}

Start state: LOCKED. Accept state: UNLOCKED (the turnstile is ready to allow entry).

What is the difference between a Mealy machine and a Moore machine?

At GCSE level, you mainly encounter simple FSMs that focus on state transitions. However, you may see a reference to two types:

• Moore machine: the output depends only on the current state. Each state circle may be labelled with an output value (e.g. a traffic light FSM where each state produces a different light combination).
• Mealy machine: the output depends on both the current state and the current input. Outputs are placed on the transition arrows rather than inside the state circles.

For GCSE (particularly OCR), the exam focuses on tracing transitions and identifying accept states. Whether the machine is Moore or Mealy is generally not examined in depth at this level.

What systems are modelled using FSMs?

FSMs are used to model any system with a finite, predictable set of conditions:

The key point is that FSMs suit systems where every possible state and transition can be enumerated in advance — they cannot model systems where the number of possible states is unlimited (for example, a calculator that must remember an arbitrarily large number would need a different model).

Frequently asked questions

How do I trace an FSM through a string of inputs?

Start in the initial state. Take the first input symbol, find the matching row in the transition table (current state + input), and move to the next state. Repeat for each subsequent input. At the end, check whether the machine is in an accept state. If it is, the input string is accepted; if not, it is rejected. Tracing through a string this way is a common exam task.

What does it mean if an FSM has no transition defined for a given input?

If no transition is defined for a particular state/input pair, the machine halts and rejects the input — this is called a trapped or dead state in some formalisms. In exam questions, transition tables are usually complete (every combination is defined), but if one is missing, assume the machine rejects that input.

What is the difference between an FSM and a flowchart?

Both show sequences of states and decisions, but they serve different purposes. A flowchart models the step-by-step logic of an algorithm, including loops, and is not constrained to a fixed set of inputs. An FSM models a system's behaviour in response to a known input alphabet, with a strictly finite number of states. FSMs are more formal and mathematical; flowcharts are more intuitive design tools.

Are finite state machines the same as regular expressions?

Formally, yes — any language described by a regular expression can be recognised by a finite state machine, and vice versa. This is the Kleene theorem. In practice, regex engines use FSM-like structures internally. At GCSE level, you do not need to prove this equivalence, but the connection helps explain why FSMs appear in the theory of computation topic.

Trace FSM diagrams, build your own transition tables, and test input strings with Professor Turing at aitutors.me.