Worked examples — Finite state machines (Mealy and Moore)

Before anything, a tiny reminder of the notation we will lean on, so no symbol appears unearned:

---

The scenario matrix

Every FSM exam question is one of these cells. The examples below each carry a tag like [Cell A] so you can see the whole space is covered.

Cell	Case class	What makes it tricky
A	Trace a Moore machine over a bit stream	output is delayed one cycle
B	Trace a Mealy machine over the same stream	output appears same cycle; watch the last symbol
C	Flip-flop count from $|S|$	the $\lceil {\log }_2\rceil$ ceiling and its degenerate values
D	Degenerate / edge inputs	empty stream, all-zeros, all-ones, reset behaviour
E	Convert Mealy $\to$ Moore	states multiply; where the extra state comes from
F	Convert Moore $\to$ Mealy	states merge; output moves onto arrows
G	Real-world word problem	turnstile / vending controller
H	Exam twist — overlapping vs non-overlapping detection	one subtle transition arrow changes everything

---

Example 1 — Trace a Moore "detect 11" machine [Cell A]

Forecast: Guess when the first 1 appears in the output — will it line up with the second input 1, or lag behind it?

1. Start in the reset state $Q=S_0$, output = 0. Why this step? Real hardware powers up unknown; the reset forces the reset state $s_0=S_0$ (defined in the symbols box above). Every trace must begin here or the answer is undefined.
2. Read input, apply $\delta$, then read the new state's output. Why this step? Moore output is $\lambda (Q)$ — but the table convention is: we clock into the next state, then that state's bubble decides the output for the following cycle. Follow the arrows in the figure.

Figure s01 — The Moore "detect 11" diagram. Read the picture like this: three violet bubbles $S_0,S_1,S_2$; the output digit sits inside each bubble (0 in $S_0$ and $S_1$, and a bold 1 in the double-ringed magenta $S_2$ — the double ring is the standard "accepting/output-high" mark). The orange arrows labelled "in=1" march you rightward $S_0\to S_1\to S_2$ as consecutive 1s arrive; the magenta arrows labelled "in=0" all sweep you back to $S_0$ because any 0 breaks the run. The small orange self-loop on $S_2$ says "another 1 keeps you saturated in $S_2$." The navy arrow into $S_0$ marks it as the reset state. When you trace below, physically hop bubble-to-bubble along these arrows.

Walking it (state shown after each input, output is that state's bubble value):

step	input	state after	output
1	1	$S_1$	0
2	0	$S_0$	0
3	1	$S_1$	0
4	1	$S_2$	1
5	1	$S_2$	1

3. Read off the output stream: $00011$. Why this step? Once two 1s are seen we stay in $S_2$ as long as more 1s keep arriving (the self-loop in the figure), so the output stays high.

Verify: The input had its first 11 completing at position 4 (the pair at positions 3–4). Output first goes high at step 4 — the cycle the second 1 lands in $S_2$. Sanity check: three total consecutive 1s (positions 3,4,5) should keep output high for the two "completed pairs" cycles (steps 4 and 5). ✓

---

Example 2 — Same stream, Mealy machine [Cell B]

Forecast: Will the Mealy 1 appear one cycle earlier than the Moore 1?

1. Start in reset $Q=A$. Why? Same reason — known start state $s_0=A$.
2. For each input, the output is decided by the arrow $\lambda (Q,I)$ we traverse, not by the state we land in. Why this step? This is the entire Mealy idea: output rides the transition, so the current input is allowed to influence it this cycle.

Figure s02 — The Mealy "detect 11" diagram, only two bubbles ($A$, $B$). Crucially, the output now lives on the arrows, written as input / output. The orange arrow $A\stackrel{1/0}{\to }B$ reads "input 1 gives output 0 and moves to $B$"; the magenta arrows labelled 0 / 0 reset you to $A$; the magenta self-loop 1 / 1 on $B$ is the money arrow — "already saw a 1, now see another 1, so emit 1 right now." As you trace, the digit you write down is the second half of the label on the arrow you walk, not anything inside a bubble.

step	state $Q$	input	arrow taken	arrow output	next state
1	$A$	1	$A\stackrel{1/0}{\to }B$	0	$B$
2	$B$	0	$B\stackrel{0/0}{\to }A$	0	$A$
3	$A$	1	$A\stackrel{1/0}{\to }B$	0	$B$
4	$B$	1	$B\stackrel{1/1}{\to }B$	1	$B$
5	$B$	1	$B\stackrel{1/1}{\to }B$	1	$B$

3. Output stream: $00011$.

Verify: Compare with Example 1. The pattern $00011$ is identical, but for a subtle reason tied to our clocking convention. Recall the convention: our Moore trace already prints $S_2$'s bubble value in the same cycle the second 1 clocks it into $S_2$ (i.e. right at the rising edge that ends step 4), so both machines number their first output-1 at step 4. The genuine timing difference is within a cycle: the Mealy 1 at step 4 is produced combinationally, the instant the input is 1 while in $B$ — before the rising edge fires, so it is available early in the cycle; the Moore 1 only exists after that rising edge parks the register in $S_2$, so it settles late in the cycle and is glitch-free. Same step number, different moment inside the cycle. ✓

---

Example 3 — Flip-flops for various state counts [Cell C]

Forecast: Does 8 states cost the same as 9? Does 1 state need zero flip-flops?

The tool is $n=\lceil {\log }_2|S|\rceil$. Why ${\log }_2$ and not, say, $|S|$ directly? Each flip-flop is one bit with 2 possible values, so $n$ flip-flops give $2^n$ distinct codes. We need $2^n\ge |S|$; solving for the smallest whole $n$ gives the ceiling of ${\log }_2|S|$.

1. $|S|=1$: ${\log }_{2}1=0$, $\lceil 0\rceil =0$. Why? One state needs no bit to distinguish it from anything — but real designs still keep at least 1 register for reset, so this is the theoretical floor.
2. $|S|=2$: ${\log }_{2}2=1\Rightarrow n=1$.
3. $|S|=3$: ${\log }_{2}3\approx 1.585\Rightarrow \lceil 1.585\rceil =2$. Why the jump? 1 flip-flop only gives 2 codes; 3 states need at least 2 bits (4 codes, one unused).
4. $|S|=5$: ${\log }_{2}5\approx 2.322\Rightarrow 3$.
5. $|S|=8$: ${\log }_{2}8=3\Rightarrow 3$. Exactly filled — all 8 codes used.
6. $|S|=9$: ${\log }_{2}9\approx 3.17\Rightarrow 4$. The exam trap: one extra state past a power of 2 forces a whole new flip-flop.

Verify (units + monotonic): $n$ must be a non-negative integer and never decrease as $|S|$ grows: $0,1,2,3,3,4$ — monotone non-decreasing ✓. Powers of two ($2,8$) sit right at the boundary: $2^1=2$, $2^3=8$ ✓.

This directly settles the parent-note mistake "more states → more flip-flops": going $2\to 3$ states costs the same 2 flip-flops after rounding.

---

Example 4 — Degenerate inputs: empty, all-zeros, all-ones [Cell D]

Forecast: Which one produces the longest run of output 1s?

1. (a) Empty stream: no inputs arrive, so no clock edge processes a symbol and the machine simply sits in its reset state $s_0=S_0$. Because $S_0$'s bubble carries output 0, the output the machine holds is $\lambda (S_0)=0$, but the output stream (one digit per input symbol) is empty since there were zero symbols. Why? No transitions fire, so we never leave the reset bubble; and with no input symbols there is nothing to produce a digit for.
2. (b) $0000$: every 0 sends us to (or keeps us in) $S_0$. States: $S_0,S_0,S_0,S_0$. Output $0000$. Why? A 0 breaks any run of 1s — this is the "reset toward $S_0$" rule.
3. (c) $1111$: states $S_1,S_2,S_2,S_2$. Output $0111$. Why? First 1 only reaches $S_1$ (no pair yet); every subsequent 1 keeps us saturated in $S_2$, which outputs 1.

Verify: Count of output-1s in (c) is $3$, matching "four 1s make three overlapping pairs." (a) and (b) have zero 1s since no pair ever forms ✓. This confirms the degenerate all-ones case is the max-output case.

---

Example 5 — Convert Mealy → Moore [Cell E]

Forecast: Will the state count go up, and by how much?

The tool: state splitting. Why this tool? A Moore state carries a single fixed output. A Mealy state like $B$ can be entered with different outputs (you reach $B$ producing a 0 via $A\stackrel{1}{\to }B$, or via $B\stackrel{1}{\to }B$ producing a 1). Moore cannot let one bubble emit two different outputs, so we must split $B$ into two Moore states — one that outputs 0, one that outputs 1.

Naming convention for the new Moore states: we write each Moore state as the pair (old Mealy state, the fixed output that state carries). So:

• $A_0$ means $(A,\text{output}=0)$ — "the memory $A$, carrying output 0."
• $B_0$ means $(B,\text{output}=0)$ — "the memory $B$, entered emitting 0."
• $B_1$ means $(B,\text{output}=1)$ — "the memory $B$, entered emitting 1."

Figure s03 — The splitting move drawn out. On the left, the single violet $A_0$ (output 0). On the right, the old Mealy $B$ has become two bubbles: violet $B_0$ (output 0, reached by the orange "1" arrow from $A_0$) and double-ringed magenta $B_1$ (output 1, reached by the orange "1" arrow from $B_0$ and by its own self-loop). Notice both $B_0$ and $B_1$ send a magenta "0" arrow back to $A_0$ — that identical behaviour is the visual proof they are the same memory ("last bit was a 1"), differing only in the output digit each carries. The side note reminds you: $B_0$ = "entered $B$ emitting 0", $B_1$ = "entered $B$ emitting 1".

1. List each (state, incoming-output) pair. $A$ is always entered producing 0 → one Moore state $A_0$. $B$ is entered producing 0 (from $A$ on 1) → $B_0$, and producing 1 (from $B$ on 1) → $B_1$. Why? Each distinct output that could be "carried into" a state becomes its own bubble.
2. Assign each Moore state its fixed output: $A_0\to 0$, $B_0\to 0$, $B_1\to 1$.
3. Rebuild transitions so they land in the correctly-outputting copy:
   • $A_0$: on 0 → $A_0$, on 1 → $B_0$
   • $B_0$: on 0 → $A_0$, on 1 → $B_1$
   • $B_1$: on 0 → $A_0$, on 1 → $B_1$ Why? $B_0$ and $B_1$ are the same memory ("last bit was a 1") but differ only in the output they emit — so their outgoing arrows are identical (see the figure).

Verify: This is exactly the 3-state Moore machine from the parent note with $A_0=S_0$, $B_0=S_1$, $B_1=S_2$. Trace $11$: $A_0\to B_0(\text{out }0)\to B_1(\text{out }1)$ — matches Example 1's one-cycle-delayed 1 ✓. State count went $2\to 3$, confirming "Moore needs more states." Flip-flops: $\lceil {\log }_{2}3\rceil =2$ (Example 3), while Mealy needs $\lceil {\log }_{2}2\rceil =1$ — so here Moore actually costs one more flip-flop, because $2\to 3$ crosses the $2^1$ boundary. Good corner case! ✓

---

Example 6 — Convert Moore → Mealy [Cell F]

Forecast: Which two states collapse into one?

The tool: state merging — the reverse of splitting. Why? $S_1$ and $S_2$ have identical outgoing transitions (both go to $S_0$ on 0 and to $S_2$ on 1); they differ only in the constant output printed in their bubble. In Mealy we can encode that output difference on the arrow that entered them, freeing us to merge $S_1$ and $S_2$ into one memory state "$B$ = last bit was 1."

Figure s04 — The merge drawn out. On the left the three Moore bubbles $S_0,S_1,S_2$ with the two right-hand ones highlighted; a violet dashed lasso groups $S_1$ and $S_2$ to show "same memory, different bubble output." On the right the collapsed Mealy machine: violet $A$ (was $S_0$) and violet $B$ (the merged $S_1+S_2$). The output that used to sit inside $S_2$ has slid onto the magenta self-loop $B\stackrel{1/1}{\to }B$ — that is the arrow which formerly carried you $S_1\to S_2$ into the output-1 bubble. The orange $A\stackrel{1/0}{\to }B$ (was $S_0\to S_1$) and the magenta $0/0$ reset arrows keep output 0.

1. Identify mergeable states. Compare rows: $S_1$ goes $\{0\to S_0,1\to S_2\}$ and $S_2$ goes $\{0\to S_0,1\to S_2\}$ — identical destinations. They mean the same fact, "the last bit I read was a 1," so merge $S_1,S_2\to B$; keep $S_0\to A$. Why? Two states with the same next-state behaviour are the same memory; their only difference (bubble output) can be pushed onto arrows in Mealy form.
2. Move each output onto the arrow that reaches the merged state. In Moore, landing in $S_2$ produced output 1. The arrow that lands you in $S_2$ and comes from a state already holding a 1 is the old $S_1\stackrel{1}{\to }{S}_2$; in the merged machine that is $B\stackrel{1}{\to }B$, so we label it output 1: $B\stackrel{1/1}{\to }B$. The arrow $A\stackrel{1}{\to }B$ (formerly $S_0\to S_1$, landing in the output-0 bubble $S_1$) keeps output 0: $A\stackrel{1/0}{\to }B$. Every 0 arrow returns to $A$ with output 0. Why? The output must be emitted exactly when the Moore machine would have been sitting in the output-1 bubble $S_2$, i.e. right as we complete the second consecutive 1 — that is the $B\to B$ on input 1 transition.
3. Result: exactly the 2-state Mealy machine of Example 2 (Figure s02), with $A\stackrel{1/0}{\to }B$, $B\stackrel{1/1}{\to }B$, and both $0/0$ resets.

Verify: Trace $11$ on the merged Mealy: $A\stackrel{1/0}{\to }B\stackrel{1/1}{\to }B$ → outputs $0,1$. The Moore original on $11$ gave $0,1$ as well (Example 1's delayed pattern). Language identical, state count $3\to 2$ ✓. And a longer check — feed $10111$: merged Mealy gives $00011$, matching Example 2 exactly ✓.

---

Example 7 — Real-world word problem: a turnstile [Cell G]

Forecast: How many of the five actions actually let someone through?

1. Choose the two states and their outputs. Moore output $Z$ = "gate is open to walk through": $\text{Locked}\to Z=0$, $\text{Unlocked}\to Z=1$. Why this step? The gate's open/closed status is a property of where we are, not of the button just pressed — that is precisely the Moore rule $Z=\lambda (Q)$, so it belongs inside the state, and we pick Moore for exactly that reason.

2. Write the transition table.

   • Locked: coin → Unlocked, push → Locked
   • Unlocked: coin → Unlocked, push → Locked

   Why this step? Each row must answer "for this state, where does each possible input send me?" — the definition of $\delta$. coin always ends Unlocked (money always unlocks); push always ends Locked (a push either passes you through and re-locks, or does nothing while locked). A coin while Unlocked stays Unlocked because it is "wasted" — no state change.

3. Trace from reset $s_0=$ Locked. Why this step? Hardware powers up unknown, so we must anchor at the defined reset state $s_0=\text{Locked}$; each row below applies $\delta$ then reads the landed state's bubble output (our Moore convention).

step	input	state after	$Z$
1	push	Locked	0
2	coin	Unlocked	1
3	push	Locked	0
4	push	Locked	0
5	coin	Unlocked	1

Why each row is what it is: step 1 pushes a locked gate → stays Locked ($Z=0$); step 2 coin → Unlocked ($Z=1$); step 3 push while unlocked → passes through and re-locks ($Z=0$); step 4 push a now-locked gate → stays Locked ($Z=0$); step 5 coin → Unlocked again ($Z=1$).

Verify (real-world sanity): Output is high (gate open) exactly after a coin: steps 2 and 5 → two people got through, matching the two coins inserted. Wasted pushes at steps 1,3,4 correctly produce 0. Units check: one coin ⟶ at most one passage ✓.

---

Example 8 — Exam twist: overlapping vs non-overlapping "111" [Cell H]

Forecast: How many 1 outputs does each flavour produce on five 1s?

States: $A$=zero 1s so far, $B$=one 1 so far, $C$=two 1s so far. Arrow labels are input / output.

1. (a) Overlapping. On the third consecutive 1, output 1 and stay in $C$ (so the just-matched 1 can be the start of the next overlap). The money arrow is $C\stackrel{1/1}{\to }C$. Why stay in $C$? Because after 111, the last two 1s ("11") are already a partial next match; staying in $C$ remembers "I still have two 1s in a row behind me."

Figure s05 — Both 111 detectors on one diagram; the single arrow leaving $C$ on input 1 is the whole exam trap. Three violet bubbles $A\to B\to C$ are chained by orange arrows labelled 1 / 0 (building up 1s, no output yet). Then two competing arrows from $C$: the magenta self-loop 1 / 1 (overlap) keeps you in $C$ and emits 1 — that is flavour (a); the violet sweeping arc 1 / 1 (non-overlap) back to $A$ also emits 1 but throws you to the start — that is flavour (b). Pick exactly one of those two arrows for your machine. (For clarity the "input 0" arrows, which all send you back to $A$ with output 0, are omitted.)

Trace $11111$ using the magenta self-loop:

step	state $Q$	input	arrow taken	output	next state
1	$A$	1	$A\stackrel{1/0}{\to }B$	0	$B$
2	$B$	1	$B\stackrel{1/0}{\to }C$	0	$C$
3	$C$	1	$C\stackrel{1/1}{\to }C$	1	$C$
4	$C$	1	$C\stackrel{1/1}{\to }C$	1	$C$
5	$C$	1	$C\stackrel{1/1}{\to }C$	1	$C$

Outputs: $00111$ → three matches (the windows at positions 1–3, 2–4, 3–5).

2. (b) Non-overlapping. On the third 1, output 1 but reset to $A$ — discard the shared bits. The money arrow is $C\stackrel{1/1}{\to }A$. Why reset to $A$? We are told matches may not share bits, so once 111 completes we throw everything away and rebuild a fresh run from zero.

Trace $11111$ using the violet arc back to $A$:

step	state $Q$	input	arrow taken	output	next state
1	$A$	1	$A\stackrel{1/0}{\to }B$	0	$B$
2	$B$	1	$B\stackrel{1/0}{\to }C$	0	$C$
3	$C$	1	$C\stackrel{1/1}{\to }A$	1	$A$
4	$A$	1	$A\stackrel{1/0}{\to }B$	0	$B$
5	$B$	1	$B\stackrel{1/0}{\to }C$	0	$C$

Outputs: $00100$ → one match (the first 111); the remaining two 1s only rebuild toward $C$ but never complete a second, non-overlapping triple.

Verify: Overlapping count = number of length-3 windows in a length-5 all-ones string = $5-3+1=3$, all of which match ✓. Non-overlapping count = $\lfloor 5÷3\rfloor =1$ ✓. This is the classic exam trap: a single transition arrow ($C\stackrel{1}{\to }C$ vs $C\stackrel{1}{\to }A$) flips the answer from 3 to 1.

---

Recall Quick self-test

Moore output for input 11 starting reset ::: $01$ (delayed one cycle). Flip-flops for 9 states ::: $\lceil {\log }_{2}9\rceil =4$. Mealy → Moore state count for the 2-state detector ::: grows to 3 (split $B$). Overlapping 111 on five 1s: number of matches ::: 3. Non-overlapping 111 on five 1s: number of matches ::: 1.

---

Connections

• Finite state machines (Mealy and Moore) — the parent note these examples drill
• Sequence detectors — Examples 1, 2, 8 are the canonical sequence-detector drills
• State encoding — Example 3's flip-flop counting is the first step of encoding
• State minimization — Example 6's state merging is minimization in action
• Flip-flops — the state register holding $Q$ in every trace
• Clocking and timing — why Moore's output lags one cycle (Examples 1 vs 2)