A-Level Computer Science / Unit 12: Software Design, Testing and Evolution

12.2.4 Modelling Behaviour with State-Transition Diagrams

🔒 Lesson slides are available to signed-in users. Sign in

12.2.4 Modelling Behaviour with State-Transition Diagrams

Some algorithms respond differently to an event depending on what has already happened. A state-transition diagram documents this behaviour by showing the possible states of the system and the events that cause movement between them.

This representation is particularly useful for controllers, user sessions, games, communication protocols and interfaces whose behaviour depends on their current condition.

By the end of this section, you should be able to:

  • Explain why state-transition diagrams are used to document algorithms.
  • Distinguish between a state, an input or event, a transition and an output.
  • Interpret and construct state-transition tables.
  • Interpret and construct state-transition diagrams.
  • Explain start states, final states and self-loops.
  • Interpret transition labels written as input | output.
  • Trace an input sequence through a finite state machine.
  • Check whether a proposed model accounts for the required behaviour.

Why Document Behaviour with States?

A normal step-by-step algorithm describes operations in an expected order. However, some systems repeatedly wait for an event and respond according to their current condition.

For example, the same event may have different effects depending on whether a parcel locker is waiting for a code, has already recorded two incorrect attempts or has opened its compartment.

State-transition diagram: a diagram that documents the behaviour of an algorithm by showing its possible states and the transitions caused by inputs or events.
Design question How a state model helps
What condition is the system currently in? The active state records the current condition.
Which events can occur now? Outgoing transitions identify relevant events.
What happens after an event? The transition identifies the next state.
Does the event produce a response? An output can be added to the transition label.
Can the process finish? A final state can represent a completed or halted process.
Exam tip: When describing the purpose, explain that the diagram records how the algorithm responds to events in different current states.

Finite State Machines

Finite state machine (FSM): a model containing a fixed number of possible states and rules that determine how inputs or events change the current state.

At any instant, the machine is in one current state. When an input is received, the machine uses both the current state and that input to determine what happens next.

A simple description of an FSM is:

Current state + input → next state and optional output

The set of states is finite because the model lists a limited number of possible conditions. This does not mean that the system can process only a limited number of events. It may move between those states many times.

Common misconception: “Finite” describes the number of possible states, not the number of times the system can run.

States, Inputs, Transitions and Outputs

Term Meaning Parcel-locker example
State A condition in which the system can remain until an event occurs. TwoFailedAttempts
Input or event Something detected by the system that may cause a response. validCode
Transition The movement from the current state to a next state. TwoFailedAttempts → CompartmentOpen
Output An action or message produced when a transition occurs. unlockCompartment

Choosing suitable states

A state should represent information that affects future behaviour. In the locker example, the number of previous failed attempts matters because a third incorrect code locks the session.

This relevant history can be stored in separate states:

  • Ready
  • OneFailedAttempt
  • TwoFailedAttempts

An alternative algorithm might use one state and a counter variable, but the state-transition model makes the changing behaviour explicit.

Common mistake: State names should describe conditions such as CompartmentOpen. Events such as enterCode normally belong on transition arrows.

State-Transition Tables

A state-transition table organises the behaviour before a diagram is drawn. Each row describes one combination of current state and input.

State-transition table: a table that associates a current state and input with a next state and, where required, an output.
Current state Input Next state Output
Ready validCode CompartmentOpen unlockCompartment
Ready invalidCode OneFailedAttempt showRetryMessage
OneFailedAttempt validCode CompartmentOpen unlockCompartment
OneFailedAttempt invalidCode TwoFailedAttempts showFinalWarning
TwoFailedAttempts validCode CompartmentOpen unlockCompartment
TwoFailedAttempts invalidCode SessionEnded lockSession
CompartmentOpen doorClosed SessionEnded confirmCollection
CompartmentOpen reminderTime CompartmentOpen soundReminder
Exam tip: Always use the pair current state and input. An input on its own may not be enough to determine the next state.

State-Transition Diagram Notation

Diagram feature Meaning
State circle A condition the system may occupy.
Labelled arrow A transition caused by the input or event written on the arrow.
Start arrow The state occupied when the model begins.
Double circle A final or halting state, when the model has one.
Arrow returning to the same state A self-loop: the event is processed without changing state.
input | output The input causes the transition and produces the named output.

The start state

The start arrow points to the state occupied before the first input is processed. In the parcel-locker session, the start state is Ready.

The final state

A final state represents a completed or halted process. The parcel-locker session reaches SessionEnded after a successful collection or after the third incorrect code.

Not every FSM needs a final state. A controller that operates continuously may keep moving between states until the whole system is switched off.

Common misconception: A state with no outgoing transitions is not automatically the start state. Start and final states have different notation and purposes.

Self-Loops and State-Preserving Events

Self-loop: a transition whose next state is the same as its current state.

A self-loop shows that the event is recognised even though the system does not move to a different state.

When the locker compartment remains open for too long: 

CompartmentOpen
    + reminderTime
    → CompartmentOpen
    + soundReminder

The reminder is produced, but the condition of the system remains CompartmentOpen.

Common mistake: Do not omit an event simply because it leaves the machine in the same state. If the event is part of the required behaviour, show the self-loop.

Outputs Produced by Transitions

Some state models show only current state, input and next state. Other models also document an output produced as the transition occurs.

The conventional label is:

input | output
Transition label Interpretation
validCode | unlockCompartment A valid code causes the state transition and unlocks the compartment.
invalidCode | showFinalWarning An invalid code produces the final warning before another attempt.
doorClosed | confirmCollection Closing the door ends the session and produces confirmation.
A finite state machine whose outputs are associated with transitions is commonly described as a Mealy machine.
Exam tip: Read the vertical bar as “produces”: doorClosed | confirmCollection means that the doorClosed event produces the confirmCollection output.

Accounting for Relevant State and Input Combinations

A useful model should define what happens for every input that is relevant in each state.

For example, doorClosed is relevant when the compartment is open, but it may have no meaning while the system is waiting for a code.

Situation Design decision
An input must change the state. Draw a transition to a different state.
An input is processed but the state remains unchanged. Draw a self-loop.
An input is ignored deliberately. Document that decision or include a self-loop if the required notation expects every relevant combination.
The scenario does not define what happens. Clarify the requirement rather than guessing silently.
Two different transitions exist for the same state and input. The design is ambiguous unless another condition distinguishes them.
Common mistake: Do not add two different arrows with the same input leaving one state unless the scenario provides an additional condition that selects between them.

Worked Example: Parcel-Locker Collection Session

A collection session begins while the locker is waiting for a customer code. A correct code opens the compartment. Three incorrect codes end and lock the session. Once opened, the compartment produces a reminder if it remains open too long. Closing the door completes the session.

Step 1: Identify the states

State Meaning
Ready No incorrect code has been entered.
OneFailedAttempt One incorrect code has been entered.
TwoFailedAttempts Two incorrect codes have been entered.
CompartmentOpen The correct compartment is unlocked and open.
SessionEnded The collection succeeded or the session was locked.

Step 2: Identify the inputs

  • validCode
  • invalidCode
  • doorClosed
  • reminderTime

Step 3: Identify the outputs

  • unlockCompartment
  • showRetryMessage
  • showFinalWarning
  • lockSession
  • soundReminder
  • confirmCollection

Step 4: Write the transitions

Ready
    validCode | unlockCompartment
        → CompartmentOpen

Ready
    invalidCode | showRetryMessage
        → OneFailedAttempt

OneFailedAttempt
    invalidCode | showFinalWarning
        → TwoFailedAttempts

TwoFailedAttempts
    invalidCode | lockSession
        → SessionEnded

CompartmentOpen
    reminderTime | soundReminder
        → CompartmentOpen

CompartmentOpen
    doorClosed | confirmCollection
        → SessionEnded

A valid code from either failed-attempt state also moves to CompartmentOpen and produces unlockCompartment.

Exam tip: The failed-attempt states are needed because the effect of invalidCode changes after each previous failure.

Method: From Scenario to State-Transition Diagram

  1. Identify changing conditions. Find the conditions that affect how later events are handled.
  2. Name the states. Use concise names that describe conditions rather than actions.
  3. Mark the start state. Decide the condition before the first input.
  4. Identify any final state. Decide whether the model can finish or halt.
  5. List inputs and events. Include user actions, sensor events and timer events where relevant.
  6. Build a transition table. Determine the next state for each relevant current-state and input pair.
  7. Add outputs. Use input | output where the transition produces a response.
  8. Draw the states and transitions. Transfer every table row to the diagram.
  9. Check self-loops and missing transitions. Confirm what happens when an event does not change the state.
  10. Trace test sequences. Follow several valid and exceptional paths through the model.
Exam tip: Constructing the transition table first reduces the chance of omitting or duplicating an arrow.

Tracing an Input Sequence

To trace an FSM, begin at the start state and process one input at a time. The next state from one transition becomes the current state for the next input.

Trace A: successful first attempt

Step Current state Input Output Next state
1 Ready validCode unlockCompartment CompartmentOpen
2 CompartmentOpen doorClosed confirmCollection SessionEnded

Trace B: three incorrect codes

Step Current state Input Output Next state
1 Ready invalidCode showRetryMessage OneFailedAttempt
2 OneFailedAttempt invalidCode showFinalWarning TwoFailedAttempts
3 TwoFailedAttempts invalidCode lockSession SessionEnded

Trace C: reminder while open

Ready
→ validCode
→ CompartmentOpen
→ reminderTime
→ CompartmentOpen
→ doorClosed
→ SessionEnded
Common mistake: Do not return to the start state before every input. Continue from the next state produced by the previous transition.

Checking a State-Transition Model

Check Question to ask Possible warning sign
State quality Does each state describe a meaningful condition? A state is named EnterCode, which is an action.
Start state Is the initial condition shown? No start arrow is present.
Final state Is a halting condition shown where required? A completed session still has unexplained outgoing transitions.
Transition labels Does every arrow identify the event that causes it? An arrow has no input label.
Outputs Are required responses attached to the correct transitions? unlockCompartment is written as a state.
Self-loops Are state-preserving events represented? The reminder event is absent from the open state.
Completeness Is every relevant state/input combination addressed? The model does not say what a valid code does after one failure.
Consistency Do the table and diagram describe the same behaviour? A table row has no matching arrow.
Exam tip: Compare the table and diagram one transition at a time. Every table row should have one matching labelled arrow.

Interactive: Parcel-Locker FSM Explorer

Choose events and observe how the current state changes. The active transition, output and transition-table row are highlighted.

Parcel-locker collection session

start invalidCode | retry invalidCode | finalWarning invalidCode | lockSession validCode | unlock validCode | unlock validCode | unlock doorClosed | confirm reminderTime | reminder
Ready
One failed
attempt
Two failed
attempts
Compartment
open
Session
ended
Current state

Ready

Choose an input to trace the collection session.

Output: --
Last transition: start → Ready
Current state Input Next state Output
Ready validCode Compartment open unlockCompartment
Ready invalidCode One failed attempt showRetryMessage
One failed attempt validCode Compartment open unlockCompartment
One failed attempt invalidCode Two failed attempts showFinalWarning
Two failed attempts validCode Compartment open unlockCompartment
Two failed attempts invalidCode Session ended lockSession
Compartment open doorClosed Session ended confirmCollection
Compartment open reminderTime Compartment open soundReminder

Common Mistakes and Misconceptions

  • Using events as state names. States describe conditions; events normally label arrows.
  • Choosing a next state from the input alone. The current state must also be considered.
  • Forgetting the start arrow. The initial state must be identifiable.
  • Assuming every machine has a final state. Continuously operating systems may have none.
  • Omitting self-loops. An event can be processed without changing state.
  • Putting outputs inside state circles. In a Mealy-style diagram, outputs belong on transition labels.
  • Reading input | output as two inputs. The value after the bar is the response produced.
  • Drawing two ambiguous transitions. One current-state and input pair should not produce two unexplained results.
  • Failing to model relevant history. If previous failures change later behaviour, that information must be stored in the states or elsewhere in the algorithm.
  • Failing to compare the table and diagram. Both representations should describe the same transitions.

Practice

Core questions

  1. Define the term finite state machine.
  2. Explain the purpose of a state-transition diagram.
  3. Distinguish between a state and an input.
  4. Explain what a labelled transition arrow represents.
  5. Explain the purpose of the start arrow.
  6. Explain when a double circle is used.
  7. Explain the meaning of a self-loop.
  8. Explain the transition label timeout | displayWarning.
  9. Explain why the current state must be considered when interpreting an input.

Scenario A: Greenhouse Vent Controller

A greenhouse vent begins closed. A high-temperature event starts opening it. A sensor reports when it is fully open. When the temperature returns to normal, the vent begins closing. A sensor reports when it is fully closed. An obstruction during closing causes the vent to reopen and sound an alarm.

  1. Identify the possible states.
  2. Identify the inputs or events.
  3. Identify any outputs.
  4. Construct a state-transition table.
  5. Draw the state-transition diagram.
  6. Identify the start state.
  7. Explain whether a final state is needed.

Scenario B: Workshop Queue Ticket

A queue terminal begins ready. Pressing the request button issues a numbered ticket and changes the terminal to ticket-issued. A duplicate press while the ticket is being printed produces a wait message without changing state. Once printing is complete, the terminal returns to ready.

  1. Identify the states.
  2. Identify the self-loop.
  3. Write all transition labels using input | output.
  4. Construct the table and diagram.
  5. Trace the input sequence: request, request, printingComplete.

Scenario C: Evaluate a Model

A student models a three-attempt access system using only the states Waiting, Accepted and Rejected. An incorrect code always returns to Waiting.

  1. Explain what information the model fails to preserve.
  2. Suggest additional states.
  3. Explain how the third incorrect attempt should differ from the first.
  4. Redraw the relevant part of the model.
Challenge: Create two different input sequences that end in the same final state but produce different output sequences.

Review

Prompt A strong response should include
Purpose of a state-transition diagram To document how an algorithm responds to events in different current states.
Finite state machine A model with a fixed set of possible states and rules for moving between them.
State The current condition of the system.
Input or event Something that may cause a transition or output.
Transition Movement from the current state to the next state.
Start state The state occupied before the first input.
Final state A completed or halting condition, when the model has one.
Self-loop A transition that returns to the same state.
input | output The input causes the transition and produces the output.
Tracing Process each input from the state reached by the preceding transition.
Final exam tip: For every transition, state: current state → input → output → next state.