State diagram and state table design: Visual walkthrough

Step 1 — The problem, drawn as a moving tape

WHAT. Imagine a paper tape sliding left-to-right past a little reading window. On the tape are 0s and 1s. Each tick of a clock, one new symbol enters the window. We call the current symbol $X$ (the input bit). We want an output $Z$ that becomes $1$ for one tick, at the very moment the last four symbols read were 1 0 1 1.

WHY. Before we can design anything, we must be crystal clear: the machine sees the tape one symbol at a time. It cannot rewind. So whatever it needs to know about the past, it must carry forward in its own little memory. That memory is the whole game.

PICTURE. The amber window shows the current bit $X$ ; the greyed bits to the left are gone forever — the machine cannot look back at them.

Figure — State diagram and state table design

Step 2 — The key idea: we only need to remember "how far along the code am I?"

WHAT. Instead of storing the entire past tape, we store one tiny fact: how many symbols of 1011, counting from the front, we have matched so far, in a row, ending at the current position.

WHY. Here is the magic that shrinks infinite history down to a handful of labels. Suppose the tape so far ended in ...11101. To decide the future, does it matter that there were three 1s earlier? No. All that matters is: the longest ending of the tape that is also a beginning of 1011. That ending is 101 — three symbols matched. Any other past detail changes nothing about what the next bit will do. We call each such "how-far-along" fact a state.

PICTURE. We line up the target 1011 and slide a marker showing how much is matched. Each marker position is a state $S_{0}, S_{1}, S_{2}, S_{3}$ .

Step 3 — One state, one bit at a time: the reasoning rule

WHAT. For every state, and for each possible incoming bit ( $X = 0$ and $X = 1$ ), we ask one question: "With this new bit tacked on, what is now the longest ending of the tape that is a beginning of 1011?" That answer is the next state.

WHY. This single rule generates every arrow with no guessing. It also guarantees completeness — the parent warns that a state table must answer both input values for every state, or the machine's behaviour is undefined. Asking the question twice per state (once for $0$ , once for $1$ ) forces us to cover all cases.

PICTURE. The decision funnel: current state + new bit → "recompute the longest matched ending" → next state (and maybe a lamp).

Step 4 — Filling every transition (all 8 cases)

WHAT. Four states × two possible bits = eight transitions. Let us grind through each with the Step 3 rule.

WHY. Missing even one case leaves a hole in the machine. We list all eight so the reader never meets a scenario we skipped — that is the whole point of a complete state table.

PICTURE. Each row of the diagram below shows the glue-and-trim for one case; the amber path is the "progress" arrow, the cyan path is the "fall-back" arrow.

Walking them one by one:

From	$X$	glue → longest matching tail	Next	$Z$	Why
$S_{0}$	0	`` + `0` → nothing	$S_{0}$	0	a lone `0` is not the start of `1011`
$S_{0}$	1	`` + `1` → `1`	$S_{1}$	0	a `1` starts a possible match
$S_{1}$	0	`1` + `0` → `10`	$S_{2}$	0	progress to two matched
$S_{1}$	1	`1` + `1` → `1`	$S_{1}$	0	`11` still ends in a single `1`
$S_{2}$	0	`10` + `0` → nothing	$S_{0}$	0	`100` matches no prefix → dead
$S_{2}$	1	`10` + `1` → `101`	$S_{3}$	0	progress to three matched
$S_{3}$	0	`101` + `0` → `10`	$S_{2}$	0	`1010` ends in `10`
$S_{3}$	1	`101` + `1` → match! overlap tail `1`	$S_{1}$	1	`1011` completes → lamp, overlap leaves `1`

Step 5 — Degenerate & edge cases (do not skip these)

WHAT. We check the awkward corners: (a) the empty tape / power-on, (b) a long run of 0s, (c) a long run of 1s, (d) back-to-back overlapping matches.

WHY. A design that only handles the "interesting" input is untrustworthy. Every corner must resolve to a defined state.

PICTURE. Four short stress-tests, each ending in a clearly labelled state; note that no bit ever leaves us stuck or undefined.

(a) Power-on / empty tape. We must start somewhere: the reset state is $S_{0}$ (nothing matched). Every real machine needs this defined starting dot.
(b) All zeros 0000.... From $S_{0}$ each 0 loops back to $S_{0}$ ; from $S_{2}$ a 0 drops to $S_{0}$ . A flood of 0s can never accidentally fire $Z$ . ✓
(c) All ones 1111.... From $S_{0}$ the first 1→ $S_{1}$ , then every further 1 loops $S_{1}$ → $S_{1}$ . A wall of 1s parks harmlessly at $S_{1}$ and never fires. ✓
(d) Overlap 1011011. This is the sharpest test; it must fire twice on the same seven-bit vector we trace just below.

Step 6 — Give the states binary clothes (state assignment)

WHAT. Software labels like $S_{0}, S_{1}, S_{2}, S_{3}$ mean nothing to hardware. We assign each a 2-bit code so a pair of flip-flops can hold it. Four states need $lo g_{2} 4 = 2$ bits.

WHY. This is the bridge from the abstract map to real silicon. Call the two memory bits $Q_{1} Q_{0}$ . Once every "Next" entry is a 2-bit number, we can later read off next-state equations and pick flip-flops (the parent's steps 6+, see Excitation Tables and Next-State Equations).

PICTURE. The four bubbles, now wearing their binary codes $Q_{1} Q_{0}$ , with the same arrows re-labelled.

The one-picture summary

Everything above collapses into a single Mealy state diagram: four bubbles $S_{0} .. S_{3}$ with their codes, eight arrows labelled X/Z, and exactly one arrow (the amber $S_{3} 1/1 S_{1}$ ) that lights the lamp.

Recall Feynman retelling — the whole walkthrough in plain words

Picture a little robot watching a ticker-tape of 0s and 1s slide past, one square at a time. It's hunting for the secret run 1, 0, 1, 1. It can't remember the whole tape, so it keeps one sticky note: "how much of the secret have I lined up right now?" — nothing ( $S_{0}$ ), just the 1 ( $S_{1}$ ), 10 ( $S_{2}$ ), or 101 ( $S_{3}$ ). Every tick a new bit arrives; the robot glues it onto its progress and keeps only the longest ending that still matches the start of the secret. That tells it which sticky note to switch to. When it's sitting on 101 and a 1 arrives, the secret is complete — it flashes the lamp $Z = 1$ — but cleverly it keeps that final 1 as the beginning of a possible next secret, so it slides to $S_{1}$ instead of forgetting everything. We checked the boring corners too: endless 0s park at $S_{0}$ , endless 1s park at $S_{1}$ , and neither ever flashes by accident. Finally we dressed each sticky note in a 2-bit code so two flip-flops can hold it, and the map became a real circuit's blueprint.

Connections

Parent: State diagram & table design
Finite State Machines — the model this walkthrough instantiates
Sequence Detectors — the family this 1011 detector belongs to
State Assignment and Reduction — Step 6 in full
Excitation Tables and Next-State Equations — the next stage (steps 6+)
Flip-Flops and Latches — the memory that stores $Q_{1} Q_{0}$
Combinational Circuits — the memoryless contrast