Finite state machines (Mealy and Moore): Question bank

Before the questions, three words you must not confuse — they appear everywhere below:

Here $Q$ means "current state", $I$ means "current input bit", $Q^{+}$ means "the state after the next clock edge", and $Z$ means "the output". $∣ S ∣$ means "how many states there are". $⌈ x ⌉$ means "round $x$ up to a whole number" — you round up because you cannot buy half a flip-flop.

True or false — justify

TF1. "A Moore machine and a Mealy machine that detect the same pattern always produce the identical output waveform."

False. They can accept the same input→output relationship, but the timing differs: Mealy asserts within the same cycle as the triggering input, Moore asserts one clock edge later, so the waveforms are shifted by a cycle.

TF2. "Adding one more state to a machine always forces you to add a flip-flop."

False. Flip-flops scale as

⌈ lo g_{2} ∣ S ∣ ⌉

. Going from 3 to 4 states still fits in 2 flip-flops (

2^{2} = 4

); only crossing a power-of-2 boundary (e.g. 4→5 states) adds a flip-flop.

TF3. "In a Moore machine the output can change in the middle of a clock cycle when the input changes."

False. Moore output is

λ (Q)

and

Q

only changes on a clock edge, so the output is stable between edges — that is exactly why Moore is called glitch-free.

TF4. "In a Mealy machine the output can change in the middle of a clock cycle."

True. Mealy output is

λ (Q, I)

; since

I

is a live combinational wire feeding the output block, a mid-cycle input change can ripple straight to the output without waiting for a clock edge.

TF5. "Every Mealy machine has a Moore machine with the same behaviour, and vice versa."

True (up to a one-cycle timing shift). Any Mealy machine can be converted to Moore by splitting states so each carries its own fixed output, and any Moore is trivially a Mealy that ignores

I

λ

. The Moore version typically needs more states and outputs delayed by one cycle.

TF6. "The number of input symbols

∣ I ∣

decides how many flip-flops you need."

False. Flip-flops store state, so the count depends on

∣ S ∣

, not

∣ I ∣

. Inputs feed the combinational next-state logic, not the state register.

TF7. "If two states have identical outputs and identical transitions for every input, the machine is broken."

False. It just means those two states are redundant and can be merged — that is precisely what State minimization does. The machine still works; it is merely larger than necessary.

TF8. "A combinational circuit is a special case of an FSM with one state."

True. With a single state

s_{0}

, the next-state function always returns

s_{0}

and the output depends only on the current input — that is exactly Combinational Logic. The "memory" degenerates to nothing.

Spot the error

SE1. "Moore output =

λ (Q^{+})

, computed from the next state."

The error: Moore output uses the current state

Q

, i.e.

Z = λ (Q)

. Reading the next state

Q^{+}

would show the result a cycle early and mislabels which clock edge the output belongs to.

SE2. "I need

⌈ lo g_{10} ∣ S ∣ ⌉

flip-flops for

∣ S ∣

states."

The error: it must be

lo g_{2}

, not

lo g_{10}

. Each flip-flop stores one binary digit, giving

2^{n}

patterns, so you solve

2^{n} \geq ∣ S ∣

, hence base 2.

SE3. "This is a Mealy diagram — I'll write the outputs inside the state bubbles."

The error: Mealy outputs go on the transition arrows because they depend on the input taken. Outputs inside bubbles is the Moore convention.

SE4. "My FSM starts in whatever state is convenient on paper, so I don't wire a reset."

The error: real flip-flops power up in an unknown state. Without a forced reset into

s_{0}

, the machine's early behaviour is undefined — you must physically drive the reset line.

SE5. "Mealy always uses fewer flip-flops than Moore because it uses fewer states."

The error: fewer states does not guarantee fewer flip-flops. 3 Moore states and 2 Mealy states both fit in

⌈ lo g_{2} 3 ⌉ = ⌈ lo g_{2} 2 ⌉ = 2

... wait — 2 states need only 1 flip-flop, 3 need 2, so here Mealy does save one; but in general the saving only appears when the reduction crosses a power-of-2 boundary.

SE6. "The output block and the next-state block are the same circuit, so I'll build one lump of logic."

The error: they compute different functions —

δ

(next state) and

λ

(output) — and in Moore they even take different inputs (

λ

ignores

I

). Sharing gates is an optimisation, not a requirement, and conflating them hides the Mealy/Moore boundary.

SE7. "Since Mealy reacts faster, I'll feed its output directly into another Mealy machine's input to save a cycle."

The error: chaining Mealy outputs into Mealy inputs creates long combinational paths (and possible glitches) that can violate timing, per Clocking and timing. Registering the output (a Moore-style barrier) is often needed to keep the design synchronous.

Why questions

WHY1. Why is the flip-flop count a ceiling of a logarithm rather than exactly

lo g_{2} ∣ S ∣

Because you cannot have a fractional flip-flop.

lo g_{2} 5 \approx 2.32

, but hardware needs a whole number of 1-bit stores, so you round up to 3, which gives

2^{3} = 8 \geq 5

codes.

WHY2. Why does a single wire — the input reaching the output block — define the entire Mealy/Moore distinction?

Because

λ

's dependency on

I

is the definition of Mealy. If that wire exists, output =

λ (Q, I)

(Mealy); if it is absent, output =

λ (Q)

(Moore). Everything else (state register, next-state logic) is identical.

WHY3. Why does Moore's output appear "one cycle late" compared to Mealy?

Moore output follows the state, and the state only updates on the clock edge after the triggering input is seen. Mealy output follows the input combinationally, so it fires within the same cycle the input arrives.

WHY4. Why can a Mealy machine "glitch" while a Moore machine cannot?

Mealy output depends on the live input

I

, so any transient wobble on

I

(or unequal gate delays) can momentarily flicker the output between edges. Moore output depends only on registered state, which is stable between edges.

WHY5. Why does merging a Mealy transition-output back into a state (Mealy→Moore) tend to increase the number of states?

A Moore state carries one fixed output, so any state that had to produce different outputs for different incoming inputs must be split into several states — one per distinct output — growing

∣ S ∣

WHY6. Why do we store state in flip-flops rather than in the combinational logic itself?

Combinational logic has no memory — its output is a pure function of current inputs. To remember history across clock edges you need an element that holds its value, which is precisely what a flip-flop provides.

WHY7. Why does State encoding (one-hot, binary, Gray) matter if the abstract FSM behaviour is fixed?

The behaviour is fixed, but the encoding changes the cost: binary uses fewest flip-flops, one-hot uses simplest/fastest next-state logic, Gray reduces switching to cut glitches and power. It trades register area against logic complexity and timing.

Edge cases

EC1. What is the smallest possible FSM, and how many flip-flops does it need?

An FSM with

∣ S ∣ = 1

state. It needs

⌈ lo g_{2} 1 ⌉ = 0

flip-flops — pure combinational logic with no memory at all.

EC2. How many flip-flops for exactly

∣ S ∣ = 4

states, and why is 4 a "sweet spot"?

⌈ lo g_{2} 4 ⌉ = 2

flip-flops, and all

2^{2} = 4

codes are used with none wasted. It sits exactly on a power-of-2 boundary, so encoding is maximally efficient.

EC3. You have

∣ S ∣ = 5

states in 3 flip-flops. What happens to the 3 unused codes?

They are unreachable/undefined states. You should either force transitions from them to

s_{0}

(safe design) or prove they can never be entered; otherwise a glitch or power-up could strand the machine in a dead code.

EC4. In a Mealy machine, what does the output do during the very first cycle after reset, before any clock edge?

It is already

λ (s_{0}, I)

— a combinational function of the reset state and whatever input is present — so it can be non-zero immediately, unlike Moore which must wait for the first edge to leave

s_{0}

EC5. Consider a self-loop transition (

δ (Q, I) = Q

). Can the output still change on that transition in a Mealy machine?

Yes. The state is unchanged, but Mealy output

λ (Q, I)

depends on

I

, so a different input on the self-loop can produce a different output even though the marker stays on the same square.

EC6. What happens if you forget to specify a transition for some input in some state (an "incomplete" table)?

The next state is undefined for that input — synthesis tools may insert a don't-care that lands anywhere. A complete, well-defined FSM must specify

δ (Q, I)

for every state–input pair.

EC7. A sequence detector receives an all-zeros input stream forever. What state does the "detect 11" Moore machine settle in?

It stays in (or returns to)

S_{0}

every cycle, since every 0 breaks any run of 1s. The output holds at 0 — a stable degenerate case with no transitions of interest.

Recall One-line summary of the whole trap set

The distinction is a single wire (input → output block); flip-flops scale as $⌈ lo g_{2} ∣ S ∣ ⌉$ not by input count or state count linearly; Moore is stable-but-late, Mealy is fast-but-glitchy; and you must always define reset, all transitions, and unused codes.

Connections

Finite state machines (Mealy and Moore) — the parent topic these traps drill
State minimization — merging redundant states (TF7, WHY5)
State encoding — code assignment and unused codes (EC3, WHY7)
Clocking and timing — glitches and combinational paths (TF3, TF4, SE7)
Flip-flops — why state lives in registers (WHY6)
Combinational Logic — the one-state degenerate FSM (TF8, EC1)
Sequence detectors — the running example (EC7)