State diagram and state table design: Worked examples

This page is the "no scenario left behind" companion to the parent topic. Before we work examples, we build a scenario matrix: a checklist of every kind of situation a state-machine problem can throw at you. Then each worked example is tagged with the cell it fills, so by the end you have seen all of them.

The scenario matrix

Every sequential-design question is really one (or a mix) of these cell classes:

Cell	Scenario class	What makes it tricky	Filled by
C1	Non-overlapping detector	after a match you must reset — the tail is thrown away	Ex 1
C2	Overlapping detector	after a match you go to the longest suffix = prefix state	Ex 2
C3	Mealy ⇄ Moore conversion	output on arrow vs output in bubble; state-count change	Ex 3
C4	Degenerate / empty input	zero bits in — what does the machine output? (nothing)	Ex 4
C5	"Dead" / trap behaviour & the all-wrong stream	every bit is the wrong bit; where do you sit?	Ex 4
C6	Both-input completeness (every state × every input)	a missing table cell = undefined circuit	Ex 5
C7	State assignment → binary next-state	turning symbolic Next into 2-bit codes	Ex 6
C8	Real-world word problem	translate English → states	Ex 7
C9	Exam twist (Mealy vs Moore output timing)	same stream, outputs land in different cycles	Ex 8

We will hit every cell. Prerequisites live in Finite State Machines, Flip-Flops and Latches, and Sequence Detectors.

Example 1 — Non-overlapping "11" detector (Cell C1)

Step 1 — list what to remember. Only two facts matter: "am I at the start of a pair?" or "have I already got one 1 of the current pair?".

$A$ = no 1 banked yet
$B$ = one 1 banked, waiting for the partner

Why this step? Non-overlapping means once a pair fires we forget everything — so we never need more than "0 or 1 bits into the current pair".

Step 2 — transitions on bit $X$ .

Present	$X = 0 \to$ Next / Z	$X = 1 \to$ Next / Z	Why
$A$	$A$ / 0	$B$ / 0	a `1` banks the first half
$B$	$A$ / 0	$A$ / 1	second `1` fires and resets (non-overlap)

Why this step? The key row is $B$ on $X = 1$ : we output 1 and jump back to $A$ . The completing 1 is used up, so it cannot start the next pair — that is exactly what "non-overlapping" means (contrast Cell C2).

Step 3 — trace 1111. Start $A$ . 1→ $B$ /0 · 1→ $A$ /1 · 1→ $B$ /0 · 1→ $A$ /1. Two pulses.

Verify: count of Z=1 over 1111 = 2, and over 111 = 1 (one full pair, one leftover). ✅

Example 2 — Overlapping "101" detector (Cell C2)

Step 1 — prefix states.

$S_{0}$ = matched nothing useful
$S_{1}$ = matched 1
$S_{2}$ = matched 10

Why this step? States = "longest prefix of 101 seen". Three prefixes ⇒ three states (the full match is announced on an arrow, Mealy-style).

Step 2 — the overlap-critical row. At $S_{2}$ (10 seen), a 1 completes 101. The trailing 1 is itself a fresh prefix, so we go to $S_{1}$ , not $S_{0}$ .

Present	$X = 0 \to$ / Z	$X = 1 \to$ / Z	Why
$S_{0}$	$S_{0}$ / 0	$S_{1}$ / 0	a `1` starts a match
$S_{1}$ (`1`)	$S_{2}$ / 0	$S_{1}$ / 0	`10` progresses; `11` still ends in one `1`
$S_{2}$ (`10`)	$S_{0}$ / 0	$S_{1}$ / 1	`100` dead → $S_{0}$ ; `101` = MATCH, overlap leaves `1`

Figure — State diagram and state table design

Why this step? The suffix 1 of 101 is also a prefix of 101 — that shared bit is the whole point of overlap (Cell C2 vs Cell C1).

Step 3 — trace 10101. $S_{0}$ →1→ $S_{1}$ /0 →0→ $S_{2}$ /0 →1→ $S_{1}$ /1 →0→ $S_{2}$ /0 →1→ $S_{1}$ /1. Two matches — because the fourth bit's match left us in $S_{2}$ -ready state via $S_{1}$ , letting the fifth bit complete again.

Verify: substrings of 10101 equal to 101 = positions {1–3} and {3–5} = 2. ✅

Example 3 — Convert that Mealy `101` detector to Moore (Cell C3)

Step 1 — where does the "1" go? In Moore the output must live in a resting state, so we add an accept state $S_{3}$ that outputs $1$ .

Why this step? A Mealy arrow can shout " $Z = 1$ " mid-transition; Moore cannot — it must arrive somewhere to display the 1.

Step 2 — table (output column now belongs to the state).

Present	Output	$X = 0 \to$	$X = 1 \to$	Why
$S_{0}$	0	$S_{0}$	$S_{1}$
$S_{1}$	0	$S_{2}$	$S_{1}$
$S_{2}$	0	$S_{0}$	$S_{3}$	on `1` we reach the accept state
$S_{3}$	1	$S_{2}$	$S_{1}$	behaves like $S_{1}$ (holds a `1`) but shows 1

Why this step? $S_{3}$ transitions identically to $S_{1}$ for the future (both "hold a trailing 1") — the only difference is $S_{3}$ displays $Z = 1$ . That is the extra state Moore pays for.

Step 3 — count. Mealy = 3, Moore = 4.

Verify: Moore state count $-$ Mealy state count $= 4 - 3 = 1$ , and $Moore \geq Mealy$ holds. ✅

Example 4 — Degenerate & all-wrong inputs (Cells C4, C5)

Step 1 — empty stream (C4). Zero bits means zero transitions: the machine sits in its initial state $S_{0}$ and produces no output pulse.

Why this step? Output only happens on a transition/clock event. No input bit ⇒ no event ⇒ $Z$ never asserts. Machines must be defined for the empty case — the answer is "0 matches".

Step 2 — all-zeros 00000 (C5). $S_{0}$ →0→ $S_{0}$ →0→ $S_{0}$ →0→ $S_{0}$ →0→ $S_{0}$ →0→ $S_{0}$ . We never leave $S_{0}$ . Zero matches.

Why this step? $S_{0}$ on $X = 0$ loops to itself — a self-loop / trap-like behaviour for the "nothing matched" state. Every wrong bit keeps us grounded; there is no way to fabricate a match from all-0s.

Verify: matches in empty string = 0; matches of 101 in 00000 = 0. ✅

Example 5 — Completeness check (Cell C6)

Worked example Statement

A student hands in this partial table for a 10 Mealy detector (overlapping). Find the missing entries so the table is complete (every state × every input).

Present	$X = 0$	$X = 1$
$P$	$P$ / 0	$Q$ / 0
$Q$	???	???

Forecast: how many cells are missing, and what should each be?

Step 1 — count required cells. 2 states × 2 input values = 4 cells. Three are filled; 1 row (2 cells) is missing.

Why this step? A state table is a total function $(state, input) \to (next, output)$ . Any blank cell = undefined behaviour = an unbuildable circuit.

Step 2 — fill row $Q$ (state $Q$ = "saw a 1").

$Q$ on $X = 0$ : 10 completes → output 1; the 0 is not a prefix of 10, so go back to $P$ .
$Q$ on $X = 1$ : 11 — still ends in one 1, stay in $Q$ , output 0.

Present	$X = 0$	$X = 1$
$P$	$P$ / 0	$Q$ / 0
$Q$	$P$ / 1	$Q$ / 0

Verify: total defined cells $= 2 \times 2 = 4$ ; on 10 the machine fires once → matches of 10 in 10 = 1. ✅

Example 6 — State assignment → binary next-state (Cell C7)

Step 1 — substitute codes.

Present (code)	$X = 0 \to$	$X = 1 \to$
$S_{0} = 00$	$00$	$01$
$S_{1} = 01$	$10$	$01$
$S_{2} = 10$	$00$	$11$
$S_{3} = 11$	$10$	$01$

Why this step? Downstream steps (K-maps, Excitation Tables and Next-State Equations) need pure bits, not symbols $S_{i}$ . Assignment is the bridge from behaviour to hardware. See State Assignment and Reduction for choosing a good code.

Step 2 — read off $S_{2}$ on $X = 1$ . $S_{2} \to S_{3}$ , and $S_{3} = 11$ . So the next-state bits are $(Q_{1}, Q_{0}) = (1, 1)$ .

Verify: $S_{2}$ code $= 10 = 2$ ; its $X = 1$ next state $S_{3}$ code $= 11 = 3$ . So $2 \to 3$ . ✅

Example 7 — Real-world word problem (Cell C8)

Step 1 — states = money banked.

$C_{0}$ = 0¢ banked, $V = 0$
$C_{10}$ = 10¢ banked, $V = 0$
$C_{20}$ = 20¢ reached, $V = 1$ (vend)

Why this step? The "history we must remember" is just how much money is in so far — not which coin came first. That collapses infinite input histories into 3 states, exactly the state-abstraction idea.

Step 2 — transitions. Input $X = 1$ means "a 10¢ coin arrived"; $X = 0$ means "no coin this cycle".

Present	Output $V$	$X = 0 \to$	$X = 1 \to$
$C_{0}$	0	$C_{0}$	$C_{10}$
$C_{10}$	0	$C_{10}$	$C_{20}$
$C_{20}$	1	$C_{0}$	$C_{10}$

Why this step? $C_{20}$ vends then resets to $C_{0}$ on no-coin (or to $C_{10}$ if a coin is already arriving — money not lost). This is the word-problem analogue of "after a match, go where the leftover input leads".

Step 3 — trace: coins arrive on cycles 1,1,0,1,1 (i.e. $X = 1, 1, 0, 1, 1$ ). $C_{0}$ → $C_{10}$ /0 → $C_{20}$ /0 (banked, vend shows next cycle) → on 0 we are in $C_{20}$ so $V = 1$ , then go $C_{0}$ → $C_{10}$ /0 → $C_{20}$ /0.

Number of cycles with $V = 1$ : exactly 1 (the cycle we rest in $C_{20}$ ).

Verify: two coins = 20¢ = one vend; total coins $= 4$ ⇒ vends $= ⌊ 4/2 ⌋ = 2$ ... but the stream 1,1,0,1,1 banks $C_{20}$ once, resets, then banks $C_{20}$ again on the last bit (not yet rested). So realized vend-cycles in these 5 steps = 1. ✅

Example 8 — Exam twist: Mealy vs Moore output timing (Cell C9)

Step 1 — Mealy trace. $S_{0}$ →(bit1 1)→ $S_{1}$ /0 →(bit2 0)→ $S_{2}$ /0 →(bit3 1)→ $S_{3}$ /0 →(bit4 1)→ $S_{1}$ /1. Mealy asserts $Z = 1$ during cycle 4 (the arrow taken on the 4th bit).

Step 2 — Moore trace. Same bits move $S_{0} \to S_{1} \to S_{2} \to S_{3} \to S_{4}$ . Moore's $Z = 1$ is displayed while resting in $S_{4}$ , i.e. it becomes visible after the 4th bit is clocked — effectively cycle 5 (start of the next cycle).

Why this step? Mealy reads the output off the transition (same cycle as the triggering bit). Moore reads it off the state you land in (one clock later). Same detection, output offset by one cycle — the classic timing twist that trips exam-takers.

Verify: Mealy assert-cycle $= 4$ ; Moore assert-cycle $= 5$ ; difference $= 1$ . ✅

Active recall

Recall Non-overlapping vs overlapping

11: pulses on 1111? Non-overlapping = 2 (pairs (11)(11)); overlapping = 3 (positions 1-2, 2-3, 3-4).

Recall Why does the empty input stream produce no output?

Output happens only on a transition/clock event; zero bits = zero events, so the machine just sits in its initial state.

Recall Moore vs Mealy detecting

1011 on the same stream — timing? Mealy asserts $Z = 1$ in the same cycle as the completing bit; Moore asserts it one cycle later (upon resting in the accept state).

Recall Why must every (state, input) cell be filled?

A state table is a total function; a blank cell means the circuit's next-state/output is undefined for that case.

Connections

Parent topic — the full design pipeline
Sequence Detectors — the family every example here belongs to
Finite State Machines — the model behind states & transitions
Excitation Tables and Next-State Equations — what Example 6's binary table feeds into
State Assignment and Reduction — choosing good binary codes
Flip-Flops and Latches — where the state bits physically live
Combinational Circuits — the no-memory contrast

On the stream 1111, how many pulses does a non-overlapping 11 detector give?

Two — pairs (11)(11); the completing 1 is consumed.

On the stream 10101, how many overlapping 101 matches?

Two — positions 1-3 and 3-5, sharing the middle 1.

How many states does the Moore 101 detector need vs the 3-state Mealy?

Four (one extra accept state that displays output 1).

Does the empty input stream ever assert Z?

No — no transitions occur, so the machine stays in its initial state with no output.