Computer Science · Lesson 14
State Machines
A state machine gives a robot or game character a clear answer to “What am I doing now?” A sensor reading, timer, or button press can move it to its next state. Test that idea with a traffic light, then guide a robot vacuum around an obstacle and back to its dock.
State Machine Simulator
Choose a demo from the panel. Predict the next state, then fire an event and compare your prediction with the transition log. In Robot Vacuum, try an obstacle before and after the battery runs low.
What Is a State Machine?
A finite state machine (FSM) has four key ingredients:
Inputs / Events — things that can happen (button press, timer, signal)
Transitions — rules: given current state + input → move to next state
Start state — where the machine begins
The critical rule: the system is always in exactly one state at a time. An event fires, a transition runs, and the system moves to the next state — never in two places at once.
Traffic Light Example
A traffic light cycles through three states, with each state transitioning to the next on a timer event:
Only three states. Only one active at a time. The transitions are completely deterministic — given the current state and the event, the next state is always exactly predictable.
Turing, Mealy, and Moore
Alan Turing (1912–1954) laid the theoretical foundation for all computing with his 1936 paper "On Computable Numbers," introducing the abstract Turing machine — essentially a state machine with infinite memory. In 1955–56, two engineers independently extended his ideas for practical circuits. George Mealy described machines whose outputs depend on both the current state and the current input. Edward Moore described machines whose outputs depend only on the current state. These three models — Turing, Mealy, and Moore — underpin every digital device built since: from traffic controllers and elevator logic to compilers, CPUs, and network protocols.
Real-World Applications
Draw the robot's rules before writing code
Use circles for states and label every arrow with the event that causes it. Start with Clean → Avoid → Clean. Add a low-battery route to Dock and Charge. What should happen if an obstacle is sensed while the robot is docking? Our model ignores that event; a real design must choose a safe rule and test it.
Then take the same diagram habit to the Arduino bumper robot build. Its physical switch replaces the vacuum's obstacle sensor, and its motors make each state visible.
See it in the Showcase & Game Pathways: Compare how character states (`IDLE → RUN → JUMP → FALL`) and enemy patrol states (`PATROL → CHASE → RETURN`) work in 2D Pathway 08 · Animation State Machines, Godot 05 · Enemies & Simple AI, and our student Showcase games.
Practice Problems
Easy1. A finite state machine can be in multiple states at the same time. True or False?
Easy2. In the traffic light state machine described in the lesson, how many distinct states are there?
Medium3. A vending machine has states: Idle → Coin Inserted → Dispensing → Idle. What event moves the machine from "Coin Inserted" to "Dispensing"?
Medium4. What is the minimum number of transitions needed for a 3-state machine to visit all states in a loop and return to the start?
Challenge5. A combination door lock needs a 3-digit code (digits 0–9). To model this minimally, how many states does the FSM need? (Count: Start, after digit 1, after digit 2, after digit 3/Unlocked, plus one Error/Reset state)
Innovator Profile · See Also