Finite state machines (Mealy and Moore): Visual walkthrough

Everything below is drawn from absolute zero. If a symbol appears, it was defined the line before.

Step 1 — What is a "state", really?

WHAT. Imagine a marker on a board. It sits on exactly one square. Each tick of a clock, we read one card — a 0 or a 1 — and the rules push the marker to a new square. A square is a state: it is the one thing the machine remembers.

WHY a marker and not a memory of the whole past? Our task only needs to know "how many 1s have I seen in a row so far?" — nothing else about history matters. That answer has only a few possible values, so a finite set of squares (a finite state machine) is enough. We never need infinite memory.

PICTURE. Three squares — the only three things worth remembering:

"seen 0 useful 1s"
"last bit was a single 1"
"just saw 11"

Figure — Finite state machines (Mealy and Moore)

Step 2 — Drawing the rules as arrows (the transition function)

WHAT. For each square we ask two questions: "If I read a 0, where do I go?" and "If I read a 1, where do I go?" Every answer is an arrow from one square to another, labelled with the card that triggers it.

WHY exactly two arrows per square? Because the input alphabet has exactly two symbols, 0 and 1. The machine must have a defined move for every symbol from every square — otherwise on some tick it wouldn't know what to do (an undefined machine is a broken machine).

PICTURE. Read each arrow aloud: from "single 1", a 1 advances us to "saw 11"; a 0 breaks the run and sends us back to the start.

Step 3 — Where does the OUTPUT come from? (the fork in the road)

WHAT. We want a light $Z$ (1 = on, 0 = off) that means "11 just happened." There are two honest places to attach that light, and this choice is the whole Mealy/Moore story:

Put the light on a SQUARE → the light is on whenever the marker sits on that square. This is Moore.
Put the light on an ARROW → the light flashes only while walking that arrow. This is Mealy.

WHY two options exist at all. "Did 11 just happen?" can be answered two ways: "am I standing on the saw-11 square?" (a fact about the square alone), or "did the card I just read complete a 11?" (a fact about the square AND the card together). Same event, two vantage points.

PICTURE. The fork: left branch labels the output inside a bubble; right branch labels it on an arrow.

Step 4 — The Moore machine: light lives on a square

WHAT. Take the three squares from Step 1. Paint the light on the "saw 11" square. Its output rule is: $Z = 1$ only when the marker sits there; otherwise $Z = 0$ .

WHY three squares here? Because the light is a property of where you are standing, we need a dedicated square that means "11 just happened" — a place to stand while the light is on. That is the third square $S_{2}$ . Moore therefore pays with an extra state.

PICTURE. Green square = light on. Notice the light is written inside the bubble.

square	read `0` →	read `1` →	light $Z$
$S_{0}$ start	$S_{0}$	$S_{1}$	0
$S_{1}$ one `1`	$S_{0}$	$S_{2}$	0
$S_{2}$ saw `11`	$S_{0}$	$S_{2}$	1

Every row of the table is one square's two arrows plus its bubble-light — read it straight off the picture.

Step 5 — The Mealy machine: light lives on an arrow

WHAT. Now throw away $S_{2}$ . Keep only two squares: "start" ( $A$ ) and "one 1 seen" ( $B$ ). Put the light on the arrow that leaves $B$ on a 1 — the arrow that completes a 11.

WHY only two squares? The question "is this a completing 1?" is answered by reading the card, so we no longer need a square that means "done." We fold that meaning into an arrow label. This is why Mealy uses fewer states (here 2 instead of 3).

PICTURE. Each arrow now carries a label card / light. The orange arrow $B 1/1 B$ is the one that lights up.

square	read `0` (next / $Z$ )	read `1` (next / $Z$ )
$A$ start	$A$ / 0	$B$ / 0
$B$ one `1`	$A$ / 0	$B$ / 1

The /1 on $B$ 's 1-arrow is the light — attached to the transition, not to any bubble.

Step 6 — Run BOTH on the same tape and watch the timing split

WHAT. Feed the identical input tape 0 1 1 0 1 into both machines, tick by tick, and record the light each cycle.

WHY this exact tape? It contains the 11 event (positions 2–3) and a broken run (the 0 at position 4), so it exercises the "advance", "fire", and "reset" behaviours all in one line.

PICTURE. Two timelines stacked. Same input row on top. The Moore light (blue) rises one tick after the second 1; the Mealy light (orange) rises on the same tick as the second 1.

Moore path: $S_{0} 1 S_{1} 1 S_{2} (Z = 1) 0 S_{0} 1 S_{1}$ → output 0 0 1 0 0, but the 1 shows up the cycle after landing on $S_{2}$ .
Mealy path: $A 1/0 B 1/1 B 0/0 A 1/0 B$ → output 0 0 1 0 0, and the 1 appears during the completing tick.

Step 7 — Edge & degenerate cases (never leave a scenario unshown)

WHAT / WHY / PICTURE, each corner the reader could hit:

(a) Power-up — the undefined square. Real Flip-flops wake up holding garbage, so the marker starts on an unknown square. We must force it to $s_{0}$ (the start square) with a reset wire, or the whole run is meaningless.

(b) An all-0 tape 0 0 0. The marker never leaves the start square; the light stays 0 forever. Both machines agree — good sanity check that a broken/empty input degenerates cleanly.

(c) A long run 1 1 1 1. Moore saturates on $S_{2}$ and keeps the light on each tick it stays there; Mealy lights up on every 1-arrow out of $B$ . Both correctly report "11 present" continuously.

(d) How many flip-flops for each machine? A flip-flop stores 1 bit → $n$ of them store $2^{n}$ patterns. To give every square a unique code we need $2^{n} \geq ∣ S ∣$ , i.e. $n = ⌈ lo g_{2} ∣ S ∣ ⌉$ (see State encoding).

Moore, $∣ S ∣ = 3$ : $n = ⌈ lo g_{2} 3 ⌉ = 2$ .
Mealy, $∣ S ∣ = 2$ : $n = ⌈ lo g_{2} 2 ⌉ = 1$ . So here Mealy also saves a flip-flop — but note 3 vs 2 states both round up to 2 bits in general; fewer states does not always mean fewer flip-flops.

The one-picture summary

Everything compresses to this: one wire decides Mealy vs Moore. In Moore, the input never reaches the output block, so the light follows the registered square (delayed, glitch-free). In Mealy, the input feeds straight into the output block, so the light reacts immediately (early, combinational). Same three hardware blocks — see Sequential Circuits — only that dashed wire moves.

Recall Feynman retelling of the whole walkthrough

We had a board game with a marker (Step 1) — the marker's square is the memory. We drew the rules as labelled arrows: read a card, follow the arrow (Step 2). Then we asked "where does the prize (light) go?" and found two honest answers: paint it on a square, or paint it on an arrow (Step 3). Painting it on a square gave the Moore machine — needs an extra "done" square, and the light turns on after you land (Step 4). Painting it on an arrow gave the Mealy machine — one fewer square, and the light flashes as you walk the completing arrow (Step 5). Running the same tape through both, they printed the same output sequence but Mealy fired one tick earlier (Step 6). We checked the corners: undefined power-up needs a reset, empty tapes stay dark, long runs stay lit, and flip-flop count is $⌈ lo g_{2} ∣ S ∣ ⌉$ (Step 7). The grand secret: it all comes down to one wire — whether the input reaches the output block (Summary).

Recall

The single wire that separates Mealy from Moore ::: the input wire $I$ going into the output block $λ$ (present in Mealy, absent in Moore). Why does Moore need an extra state for "detect 11"? ::: the light lives on a square, so it needs a dedicated square meaning "just saw 11" to stand on while lit. On the tape 0 1 1 0 1, when does each light fire? ::: Mealy on the same tick as the second 1; Moore one tick later. Flip-flops for a 3-state Moore machine? ::: $⌈ lo g_{2} 3 ⌉ = 2$ .

Connections

Finite state machines (Mealy and Moore) — the parent this walkthrough derives
Flip-flops — the marker's physical memory (state register)
Combinational Logic — builds the $δ$ and $λ$ blocks
State encoding — assigning binary codes to squares
Clocking and timing — why Moore is glitch-free, Mealy can glitch
Sequence detectors — the "detect 11" family used here
Sequential Circuits — the three-block clocked skeleton