State diagram and state table design: Question bank

First — the words and pictures this page leans on

Before you touch a single trap, we pin down the two letters and two terms that appear everywhere below. Nothing here is a trap; it is the ground the traps stand on.

Now the reference picture. Everything in "Spot the error" and the edge cases points back to this exact Mealy machine for the overlapping 1011 detector — glance at it whenever a state name appears.

Figure — State diagram and state table design

Worked example The same machine as a state table

Read a row as: "in this present state, for each input value, go to this next state and emit this output $Z$ ."

Present state	$X = 0$ → Next / $Z$	$X = 1$ → Next / $Z$
$S_{0}$ (nothing matched)	$S_{0}$ / 0	$S_{1}$ / 0
$S_{1}$ (matched `1`)	$S_{2}$ / 0	$S_{1}$ / 0
$S_{2}$ (matched `10`)	$S_{0}$ / 0	$S_{3}$ / 0
$S_{3}$ (matched `101`)	$S_{2}$ / 0	$S_{1}$ / 1

Notice the table is complete: every (state, input) pair has an entry. That completeness is exactly what several traps below violate.

True or false — justify

A Moore machine can always be built for any behaviour a Mealy machine can express.

True — but it may need extra "output display" states, so the Moore version has ≥ as many states as the equivalent Mealy machine.

A Mealy machine's output

Z

can change within a clock cycle if the input

X

changes.

True — Mealy output depends on present state and current input

X

, so a mid-cycle change in

X

ripples straight to

Z

(this is the glitch risk).

A Moore machine's output

Z

is stable for the whole clock period.

True —

Z

depends only on present state, which holds fixed between clock edges, so it changes only after an edge.

Two histories that lead to identical future behaviour must be encoded as different states.

False — they belong to the same state; a state is the equivalence class of histories that share identical futures.

Adding more states always makes a design more correct.

False — redundant states waste flip-flops and can hide bugs; state reduction merges equivalent states without changing behaviour.

In an overlapping sequence detector, after a match you must always return to the start state.

False — you return to the state matching the longest proper suffix of the pattern that is also a prefix; for 1011 the trailing 1 sends you to

S_{1}

, not

S_{0}

A state table with a next-state entry missing for some (state, input) pair is still a valid complete design.

False — unless that entry is an intentional don't-care, the machine's behaviour is undefined for that case, which is a design error.

Choosing

S_{0} = 00, S_{1} = 01, S_{2} = 10, S_{3} = 11

versus any other code assignment changes what the machine detects.

False — state assignment only changes the flip-flop equations and hardware cost, never the observable behaviour.

A purely combinational circuit is just a state machine with exactly one state.

True — with one state there is no history to remember, so

Z

depends only on current

X

, which is exactly combinational behaviour (see the minimal example in "Why questions").

Spot the error

(Check each claim against the reference diagram and state table above.)

"This is Mealy because it has arrows labelled X/Z, but I also wrote the output inside each bubble."

Contradiction — pick one convention: Mealy puts

Z

on arrows (as

X / Z

), Moore puts

Z

inside bubbles. Writing both means the diagram isn't a well-defined machine of either type.

"For 1011 overlap detection, I sent

S_{3}

on input

X = 1

back to

S_{0}

with

Z = 1

Wrong next state — the match ends in 1, a valid prefix, so overlap requires going to

S_{1}

(the table row for

S_{3}

confirms

S_{3} 1/1 S_{1}

). Sending it to

S_{0}

misses inputs like 1011011.

"At

S_{2}

(10 seen), input

X = 0

gives 100, so I go to

S_{1}

Wrong — 100 shares no useful prefix of 1011 (its tails 0, 00 match nothing), so it must go to

S_{0}

, the empty-match state, exactly as the table shows.

"My Moore detector has 4 states, same as the Mealy one, and both are correct."

Suspicious — Moore needs a dedicated accept state to display

Z = 1

, so it typically needs 5 states here. Four states usually means you illegally attached output to a transition.

"At

S_{1}

(1 seen), input

X = 1

gives 11, so I reset to

S_{0}

Wrong — 11 still ends in a single 1, which is a valid prefix of 1011, so you stay in $S_{1}$ (self-loop in the diagram), not reset.

"I labelled a Mealy transition X=1 with no output slash, meaning output is 0."

Ambiguous/error — every Mealy arrow must show

X / Z

explicitly; omitting the

Z

leaves the output undefined rather than implying zero.

"The output only depends on inputs, so this must be a Moore machine."

Wrong reasoning —

Z

depending purely on

X

(ignoring state) is combinational, not Moore. Moore output depends on the present state.

Why questions

Why can't a sequential circuit just store the entire input history?

History is unbounded, needing infinite memory; states compress it to a finite set of "everything you need to remember," which is what makes the circuit buildable.

Why does the Moore version need one extra state compared to Mealy for the same detector?

Moore can only signal

Z = 1

by arriving in a dedicated accept state, whereas Mealy can shout

Z = 1

during the transition without a new state.

Why must a state table specify both values of

X

for every present state?

The circuit will receive every possible input in every state; leaving one blank makes the flip-flop next-state undefined for that case, so the hardware behaves unpredictably.

Why is a Mealy machine often "faster" in reacting than Moore?

Mealy output responds to the current input

X

in the same cycle, while Moore output only updates after the next clock edge, so Moore reacts one clock later.

Why does defining states by "longest matched prefix" guarantee a finite machine?

A fixed target pattern has only finitely many prefixes, and only which prefix you've matched affects the future — so the set of distinct memory conditions is finite.

Why do we assign binary codes to states before deriving next-state equations?

Next-state equations are Boolean functions of bits; states must be numbers, not names, before you can write and minimise those equations.

Why is a Moore output truly "glitch-free" while Mealy can glitch — at the gate level?

In Moore,

Z

is computed only from the flip-flop outputs, which are held rock-steady between clock edges; so even while the input logic churns,

Z

cannot move until the next edge latches new state. In Mealy,

Z

is computed from state and the live input

X

, whose wire may momentarily settle through intermediate values (unequal gate delays on different paths), briefly driving

Z

to a wrong transient value — a hazard. Because Mealy exposes that combinational path to the output, the transient is visible; Moore hides it behind the flip-flop.

Why is a one-state FSM literally the same as combinational logic — show it.

With a single state

S_{0}

, every input leaves you in

S_{0}

(nowhere else to go), so the "memory" carries no information. The output reduces to a table of

Z

versus

X

alone: e.g. a one-state machine with

S_{0} 0 S_{0} / Z = 0

and

S_{0} 1 S_{0} / Z = 1

is just the identity gate

Z = X

— pure combinational logic, no flip-flop needed.

Edge cases

What does a Moore machine actually output at the very first instant after reset, before any input arrives?

It immediately shows the output of the reset state — because Moore output depends on state alone, and you are already sitting in

S_{0}

(whose

Z

0

here). So the learner sees a defined value (

Z = 0

) from cycle zero, no input required.

What is the output of a Mealy machine on the very first clock cycle before any bit has arrived?

Undefined until the first input is applied — Mealy output needs a current input

X

, so at reset with no

X

the output is not yet meaningful (contrast the Moore case just above).

If the input stream is empty, does a 1011 detector ever output

Z = 1

No — with no input bits it stays in the reset state

S_{0}

and never reaches the match, so

Z

stays 0.

For overlap detection of a pattern with no self-overlapping suffix (e.g. 100), where do you go after a match?

Back to

S_{0}

— no proper suffix of 100 is also a prefix, so no overlap is possible and resetting to start is correct.

A machine has an unreachable state in its table. Is the design wrong?

Not necessarily wrong, but wasteful — an unreachable state can be removed by reduction without changing behaviour, saving flip-flops.

What happens if two different states have identical outputs and identical next-state behaviour for every input?

They are equivalent (same sticky note) and should be merged into one state; keeping both is redundant and only increases hardware.

Can a state legally transition to itself?

Yes — a self-loop means "this input keeps me in the same memory condition," e.g.

S_{0}

X = 0

stays at

S_{0}

because a lone 0 starts no match.

If a Moore accept state receives an input that starts a new match, what must it do?

It transitions like the state matching that overlap prefix (for 1011, the accept state acts like

S_{1}

on a fresh 1) — it holds an output and keeps tracking the next possible match.

Connections

Finite State Machines — the abstract model these traps live in
Sequence Detectors — the canonical source of overlap misconceptions
State Assignment and Reduction — redundant/equivalent-state edge cases
Excitation Tables and Next-State Equations — why codes come before equations
Combinational Circuits — the "one state" boundary case
Flip-Flops and Latches — where incomplete tables become undefined hardware