Mr. Scandrett's ClassroomOS

Computer Science · Lesson 14

State Machines

Automata Theory Finite States Transitions Turing Mealy / Moore

A state machine is one of computing's most powerful ideas: a system is always in exactly one "state," and events cause it to move to a new state. Traffic lights, vending machines, video game characters, and TCP/IP connections all work this way.

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.

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.

State Machine Simulator

Choose a demo from the panel. Interact with the action buttons to fire events and watch state transitions happen in real time.

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

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.

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