State diagram

Also called: state transition diagram, state graph, bubble diagram

A drawing of a finite state machine: each circle is a state and each arrow a transition, labeled with the input that causes it and, for Mealy, the output.

A state diagram is the picture of a finite state machine.

Each circle is a state. A moore machine also writes the output inside, for example S1 / 1.
Each arrow is a state transition, labeled with the input value that makes it happen. A mealy machine labels arrows input/output, for example 1/0.
An arrow that comes straight back to its own circle is a self loop: "stay here on this input".
One state is marked as the initial state.

To find the next state, start at the present state, find the arrow leaving it with the input's label, and follow it. Arrows are one-way: an arrow from S0 to S1 says nothing about getting back.

A complete diagram has exactly one arrow out of every state for every input combination. With one input bit that's two arrows per state; with k input bits, 2ᵏ. That's how you know the machine never gets stuck or has to guess.

The same information can be written as a state table, which is easier to turn into equations. The diagram is easier to read and to design with.

Worked examples

Example

Reading a diagram

The diagram is a Moore machine with states Even (output 1) and Odd (output 0). It starts in Even. Apply 0, 1, 0, 0.

1.
Input 0: Even → Odd. Output 0.
2.
Input 1: Odd → Odd (self-loop). Output 0.
3.
Input 0: Odd → Even. Output 1.
4.
Input 0: Even → Odd. Output 0.
5.
Meaning check: three 0s were seen, an odd number, so ending in Odd is right ✓.

Example

Is the diagram complete?

A machine has inputs X and Y and 4 states. How many arrows must its diagram have?

1.
Two input bits give 2² = 4 input combinations.
2.
Each state needs one arrow per combination: 4 arrows per state.
3.
4 states × 4 = 16 arrows, counting self-loops.

Common mistakes

Leaving out self-loops. "Nothing happens on 1" still needs an arrow from the state back to itself.
Following an arrow into a state instead of out of it.
Writing Mealy outputs inside the circles, or Moore outputs on the arrows.

Practice State diagram

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

Counters lesson full course

Finite State Machines lesson full course

And 5 more in the Finite State Machines lesson.

Practice exams

Learn it step by step

State diagram is taught in Finite State Machines.

Finite State Machines →

All terms