Computer Science · Lesson 14

State Machines

Automata Theory Finite States Transitions Turing Mealy / Moore

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.

Current StateRED
Last Event—
Steps0
Transition log will appear here…

What Is a State Machine?

A finite state machine (FSM) has four key ingredients:

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:

🔴 RED → timer → 🟢 GREEN → timer → 🟡 YELLOW → timer → 🔴 RED

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

🚦
Traffic Control Systems Every intersection controller is a state machine. States encode which direction has the green light; timers and sensor inputs drive transitions to keep traffic flowing safely.
📱
UI Navigation Flows Modern app routers are state machines. Each screen is a state; user actions (tap, swipe, back button) are events that fire transitions between views.
🌐
TCP/IP Protocol A TCP connection moves through states: CLOSED → SYN_SENT → ESTABLISHED → FIN_WAIT → TIME_WAIT → CLOSED. Every packet received is an event that may trigger a state change.
🎮
Game Character AI Enemy characters use FSMs to manage behaviour: Idle → Patrol → Chase → Attack → Flee. The player's proximity and health level trigger transitions between states.
🤖
Robot Behavior Architecture The 2002 iRobot Roomba made autonomous floor cleaning a practical home product. Our simplified classroom model uses Clean → Avoid → Clean, with Low Battery → Dock → Charge as another route. Actual models vary; a robot also needs sensors and motion control. Compare Roomba's robotics lineage and build your own state machine.
Leave It to Roll-Oh (1940): An imaginative domestic robot introduces how real relays, microswitches, and automated finite state logic revolutionized factory and automotive control.

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?

Hint: "Finite" state machine means the system is in exactly one state at any moment. (Non-deterministic FSMs can be in multiple states, but a standard FSM cannot.)

Easy2. In the traffic light state machine described in the lesson, how many distinct states are there?

Hint: RED, GREEN, YELLOW — three states, cycling in order.

Medium3. A vending machine has states: Idle → Coin Inserted → Dispensing → Idle. What event moves the machine from "Coin Inserted" to "Dispensing"?

Hint: Once money is in, the user presses a product button — that "select product" event triggers the dispense transition.

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?

Hint: A → B → C → A requires exactly 3 transitions (one per hop in the loop).

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)

Hint: Start → Digit1Entered → Digit2Entered → Unlocked → (back to Start) plus an Error state = 5 states minimum.

Innovator Profile · See Also