Finite state machine

Also called: FSM, state machine, finite-state machine, finite automaton, sequential machine

A sequential circuit with a finite set of states, a starting state, and rules that pick the next state and the outputs from the present state and inputs.

A finite state machine (FSM) is a disciplined way to use memory. At any moment the circuit is in one of a fixed, finite set of states. At each active clock edge it takes exactly one transition, to a next state chosen by the present state and the inputs.

An FSM is fully described by:

its states, including an initial state;
its inputs and outputs;
the next-state rule, drawn as a state diagram or written as a state table;
the output rule.

In hardware it's always three parts:

a state register of flip-flops holding the present state;
next-state logic, combinational gates that compute the next state from the state and inputs;
output logic, gates that compute the outputs.

The output rule gives the two families. In a moore machine the outputs depend only on the state. In a mealy machine they also depend on the present inputs.

FSMs run traffic lights, vending machines, serial receivers, the control unit of a CPU and every sequence detector. A counter is an FSM too, usually one with no inputs besides the clock.

Worked example

Example

Tracing a Moore FSM

The diagram is a Moore machine that outputs 1 after two 0s in a row (overlapping). Start in S0 and apply 1, 0, 0, 0, 1.

1.
Input 1: S0 → S0 (self-loop). Output 0.
2.
Input 0: S0 → S1. Output 0.
3.
Input 0: S1 → S2. Output 1: two 0s seen.
4.
Input 0: S2 → S2. Output 1: the last two inputs are still 0, 0.
5.
Input 1: S2 → S0. Output 0.
6.
Outputs: 0, 0, 1, 1, 0.

Common mistakes

Thinking the machine can take two arrows at one clock edge. It takes exactly one per edge, and a self-loop counts as one.
Forgetting that a state diagram must have an arrow for every input in every state.
Treating any circuit with flip-flops as "not an FSM". Counters, registers with control, and CPUs are all FSMs.

Practice Finite state machine

Interactive questions with instant feedback and a worked solution for every wrong answer.

Basic CPU / Computer Architecture lesson full course

Practice exams

Learn it step by step

Finite state machine is taught in Finite State Machines.

Finite State Machines →

All terms