Exercises — Finite state machines (Mealy and Moore)

Moore. What we looked at: the output 1 is written inside the state bubble $\boxed{S_2/1}$, attached to the state $S_2$ itself, not to any arrow. Why that settles it: Moore's output function is $\lambda (Q)$ — it depends on the state only. A value that "belongs to a state" is exactly a Moore output. A Mealy output would be printed on a transition arrow as input / output, because $\lambda (Q,I)$ also needs to know the input.

Mealy, and the label reads input / output.

• Left of the slash = the input symbol that causes this transition (here input 1).
• Right of the slash = the output produced while taking this transition (here output 0). Why Mealy: the output is attached to the arrow, so it depends on both the state you left AND the input you read — that is $\lambda (Q,I)$, the Mealy signature.

False. Why: a combinational circuit's output depends only on the current inputs — it has no memory element. Remembering "how many 1s so far" requires storing information across clock cycles, which needs flip-flops. A circuit with memory is precisely a sequential circuit / FSM.

Use the encoding-width formula $n=\lceil {\log }_2|S|\rceil$. What each piece means: each flip-flop stores one bit, so $n$ flip-flops give $2^n$ distinct patterns. We need at least one pattern per state: $2^n\ge |S|$. ${\log }_{2}5\approx 2.32\Rightarrow n=\lceil 2.32\rceil =3.$ Check: $2^2=4<5$ (too few), $2^3=8\ge 5$ (enough). So 3 flip-flops. See State encoding for which code to assign each state.

Moore (3 states $S_0,S_1,S_2$): $n=\lceil {\log }_{2}3\rceil =\lceil 1.58\rceil =2$. Mealy (2 states $A,B$): $n=\lceil {\log }_{2}2\rceil =\lceil 1.00\rceil =1$. The surprise checked: going from 3 states to 2 states for this specific detect-11 machine does save a flip-flop ($2\to 1$). But saving a state does not always save a flip-flop — see Exercise 2.3. The ceiling only "jumps" at powers of two.

$\lceil {\log }_{2}4\rceil =2$ and $\lceil {\log }_{2}3\rceil =\lceil 1.58\rceil =2$. Answer: no — still 2 flip-flops. Why, walked through the ceiling step by step: the ceiling function $\lceil x\rceil$ holds one flat plateau for each whole-number output. Everything with $1<x\le 2$ rounds up to $2$. Now ${\log }_{2}3=1.58$ and ${\log }_{2}4=2.00$ both sit inside that same $(1,2]$ window, so both land on the plateau value $2$ — the function does not "step down" between them. It only steps to a lower plateau ($n=1$) once ${\log }_2|S|\le 1$, i.e. when $|S|\le 2$. So dropping 4→3 stays on plateau 2; only 3→2 would fall to plateau 1. The minimization may still save combinational logic (fewer transitions to decode), just not registers.

Start in the reset state $S_0$ (the one with the incoming "reset" arrow). Moore rule: the output printed is the output of the state you are currently in, read before the next input moves you.

Output stream: 0 0 1 1 0. Why there is a step 4 (an output with no input): a Moore output is read from the state you are sitting in, and after consuming the 4th input (0) you land in a new state $S_0$. That landing is itself observable — the machine now is in $S_0$ and shows $S_0$'s output 0. So $k$ inputs walk you through $k+1$ occupied states, and Moore emits one symbol per occupied state ⇒ $k+1$ output symbols. Step 4 is the output of the final landing state, not a phantom. Reading the timing: the first 1 in the output appears at step 2 — one cycle after the second input 1 (the 11 completed between step 1 and step 2). Then the third input 1 keeps us in $S_2$, so we output 1 again. This "one cycle late, then held" is the Moore timing fingerprint.

Start in reset state $A$ (incoming "reset" arrow). Mealy rule: the output is produced on the transition arrow, so it is decided by the (current state, input) pair — read the output as you take the step.

Output stream: 0 1 1 0. Compare to Moore's 0 0 1 1 0: Mealy fires 1 at step 1 — the same cycle the second 1 arrives, one cycle earlier than Moore. Also note Mealy produces exactly one output per input (one symbol per arrow taken), so 4 inputs give 4 outputs; Moore gave 5 because it also emits from the final landing state (see 3.1). That "one extra symbol" is a Moore-vs-Mealy bookkeeping difference, not a difference in what is detected.

The Mealy output can flicker; the Moore output cannot. Why: in a Mealy machine the input wire feeds directly into the output logic ($\lambda (Q,I)$). If $I$ momentarily dips to 0, the combinational output re-evaluates immediately and momentarily drops — a glitch. In a Moore machine the output depends on $\lambda (Q)$ only; $Q$ is stored in a flip-flop and changes only on a clock edge. A mid-cycle input glitch never reaches the output logic, so the output stays rock-steady until the next edge. This is exactly why Moore is called glitch-free / synchronous.

Step 1 — What must each state remember? To know if we just saw 10, we must track: have we seen a 1 that could start the pattern?

• $R_0$ (reset): "no 1 pending" (start) — output 0
• $R_1$: "last bit was 1" — output 0
• $R_2$: "just completed 10" — output 1

Step 2 — Fill $\delta$ by asking, for each state, where do 0 and 1 send me? (The reset state $R_0$ is the one with the incoming "reset" arrow when drawn.)

Why these arrows:

• From $R_1$ (a 1 is pending) a 0 completes 10 → go to $R_2$. A 1 keeps a fresh pending 1 → stay $R_1$.
• From $R_2$ a 1 starts a new possible pattern → $R_1$; a 0 breaks it (00 has no pending 1) → $R_0$.

Step 3 — Flip-flops: $|S|=3\Rightarrow n=\lceil {\log }_{2}3\rceil =2$.

Test on 1 0 1 0 (starting in reset $R_0$): $R_0\to R_1\to R_2\to R_1\to R_2$. Outputs read from current state each step: 0 0 1 0 1. The 1s land the cycle after each 10 completes — correct Moore timing. See Sequence detectors.

Key idea: the "completing 0" can be tested on the transition, so we don't need a dedicated $R_2$ state — we fold it into an arrow label.

• $A$ (reset): "no 1 pending" (start)
• $B$: "last bit was 1"

Why the 1 sits on $B$—0→$A$: being in $B$ means "a 1 is pending"; reading a 0 right now is the completion of 10, so we emit 1 on that very transition, then land back in $A$.

Flip-flops: $|S|=2\Rightarrow n=\lceil {\log }_{2}2\rceil =1$. Test on 1 0 1 0 (starting in reset $A$): $A$—1/0→$B$—0/1→$A$—1/0→$B$—0/1→$A$. Output 0 1 0 1. Fires the same cycle the completing 0 arrives — Mealy is one cycle earlier and uses one fewer state (2 vs 3) and one fewer flip-flop (1 vs 2).

Step 1 — What must be remembered? Only one fact: "have we passed the first 1 yet?" That's a single bit of memory ⇒ two states.

• $C$ (reset, copy mode): still looking for the first 1; pass input through unchanged.
• $V$ (invert mode): first 1 already seen; invert everything from now on.

Step 2 — Mealy table (output on the arrow, decided by state + current bit):

Why each entry:

• $C$, read 0: haven't hit the first 1 yet, copy it (out 0), stay copying.
• $C$, read 1: this is the first 1 — still copied unchanged (out 1), but now switch to invert mode ($V$).
• $V$, read 0: invert → out 1. $V$, read 1: invert → out 0.

Step 3 — Trace 1 0 1 1 (LSB first). Start in reset $C$:

Output (LSB first): 1 1 0 0. Sanity check as numbers. Input LSB-first 1 0 1 1 is the value $1+0\cdot 2+1\cdot 4+1\cdot 8=13$, i.e. 1101 as a 4-bit unsigned = the signed value $-3$ in 4-bit 2C. Its negation is $+3$ = 0011 = LSB-first 1 1 0 0. ✓ Matches our output stream exactly. Flip-flops: $|S|=2\Rightarrow n=1$.

Merge rule (Moore→Mealy): a Moore output that "lives in" a landing state can instead be emitted on every arrow that enters that state. In the Moore machine, state $S_2$ (output 1) is entered by exactly two arrows: "$S_1$ on input 1" and "$S_2$ on input 1". So we label those two arrows with output 1; then $S_2$ no longer needs its own output identity and can merge with $S_1$'s "one 1 already pending" role.

Resulting 2-state Mealy machine ($A$ = "no pending 1", reset; $B$ = "one 1 pending"):

Why this is minimal: the only reason Moore needed a third state was to hold the "detected" output value. Once the detection is answered by looking at the current input on a transition, that third state has no remaining job and disappears. Two states is the floor because we still must distinguish "did the previous bit leave a pending 1?" — one genuine bit of memory.

Timing proof on 0 1 1 0 1:

Moore run (output = current-state output; $k=5$ inputs ⇒ 6 occupied states ⇒ 6 symbols), start in reset $S_0$:

Moore output: 0 0 0 1 0 0.

Mealy run (output on each arrow; 5 inputs ⇒ 5 symbols), start in reset $A$:

Mealy output: 0 0 1 0 0.

Reading the shift: the Mealy 1 occurs at step 2 — the exact transition that reads the second 1 of the 11. The Moore 1 occurs at step 3 — one cycle later, when the machine has landed in $S_2$. Align both to the input that triggered them and they mark the identical 11 position; the only difference is Moore's one-cycle registration delay (plus its one extra final-landing symbol). This confirms the Mealy/Moore boundary is timing, not behaviour.