Show understanding of the purpose of state-transition diagrams to document an algorithm
12.2 Program Design: State‑Transition Diagrams
State‑transition diagrams (also called state charts) are a visual way to show how an algorithm moves from one state to another in response to inputs. Think of them as a flowchart that focuses on the “state” of the system rather than the sequence of steps.
What is a State‑Transition Diagram?
A state‑transition diagram consists of:
- States – represented by circles or ovals (e.g., $S_0$, $S_1$)
- Transitions – arrows that show how the system moves from one state to another
- Inputs/Events – conditions that trigger transitions (labelled on arrows)
- Actions – what the system does when a transition occurs (often written inside the arrow)
Why Use State‑Transition Diagrams?
They help you:
- Visualise complexity – see all possible states at a glance.
- Detect missing cases – if a state has no outgoing transition for a possible input, you’ve spotted a bug.
- Communicate clearly – examiners can quickly understand your algorithm’s logic.
How to Draw One?
- Identify all states the algorithm can be in.
- List all possible inputs/events.
- For each state‑input pair, decide the next state and any action.
- Draw circles for states, arrows for transitions, and label arrows with input → action → next state.
Analogy: Traffic Light 🚦
Think of a traffic light:
- States: Red, Yellow, Green
- Input: Timer expires
- Action: Change light colour
- Transition: Red → Green → Yellow → Red …
Just like the traffic light, your algorithm cycles through states based on inputs.
Example: Turnstile 🚪
Consider a simple turnstile that locks and unlocks when a coin is inserted.
| State | Input | Action | Next State |
|---|---|---|---|
| Locked | Insert Coin | Unlock | Unlocked |
| Unlocked | Pass Through | Lock | Locked |
| Unlocked | Insert Coin | No Action | Unlocked |
Exam Tip: When drawing a diagram, start by writing down all states and possible inputs. Then, for each combination, note the next state and any action. This systematic approach reduces the chance of missing a transition.
Practice Exercise
Design a state‑transition diagram for a simple coffee machine that can:
- Accept coins (5¢, 10¢, 25¢)
- Make coffee when at least 50¢ has been inserted
- Return change if more than 50¢ is inserted
Try to identify:
- States (e.g., $S_0$ – no money, $S_1$ – 5¢, etc.)
- Inputs (coin types)
- Actions (dispense coffee, return change)
- Transitions
Key Takeaways
- State‑transition diagrams focus on states and transitions, not just steps.
- They are excellent for spotting missing cases and simplifying complex logic.
- Use clear labels: input → action → next state.
- Practice drawing diagrams for everyday systems (turnstiles, vending machines, traffic lights).
Final Exam Tip: In the exam, you can sketch the diagram on your answer sheet. Label each state clearly, write the input and action on the arrow, and make sure every possible input has a transition from each state. This demonstrates thoroughness and will earn you full marks.
Revision
Log in to practice.