State diagram and state table design
WHY do we need states at all?
WHY this matters: A combinational circuit's output depends only on current inputs. A sequential circuit's output depends on current inputs plus history. We encode "history" into a finite set of labels (states), so the circuit only ever needs to store which state it is in, not the whole input stream.
Mealy vs Moore — WHAT is the difference?
HOW to design: the recipe
This note focuses on steps 1–5 (the "capture the behaviour" half). Steps 6+ (K-maps, flip-flop excitation) come later.
Worked Example 1 — "1011" sequence detector (Mealy, overlapping)
Spec: Output for one cycle whenever the input serial bit stream ends in the pattern 1011. Overlapping allowed (the last bits of one match can start the next).
Step 1 — WHAT must we remember?
We only care about how much of the target prefix we have seen so far. Define states by the longest prefix of 1011 currently matched:
- = matched nothing (or a useless prefix)
- = matched
1 - = matched
10 - = matched
101
Why this step? These four prefixes are the only facts about the past that change what a future bit means. Any longer history is irrelevant → finite states.
Step 2 — build transitions (Forecast-then-Verify)
At (101 seen), if next bit is 1 → we complete 1011 → output . Forecast: where do we go after matching? Because overlap is allowed, the trailing 1 of 1011 is itself a fresh 1 prefix → go to , not . Verify: input 10111011 — check it detects two matches. It does. ✅
Let's reason each transition. On input bit :
| Present | X=0 → Next / Z | X=1 → Next / Z | Why? |
|---|---|---|---|
| / 0 | / 0 | a 1 starts a possible match |
|
(1) |
/ 0 | / 0 | 10 progresses; 11 still ends in one 1 |
(10) |
/ 0 | / 0 | 100 dead → ; 101 progresses |
(101) |
/ 0 | / 1 | 1010 ends in 10 → ; 1011 = MATCH, overlap leaves 1 |
Step 3 — state assignment
Pick . Now every "Next" entry becomes a 2-bit number, ready for flip-flop equations.
Worked Example 2 — Moore version of the same detector
In Moore, the output belongs to a state, so we need an extra "accept" state that outputs 1.
| Present | Output | X=0 → Next | X=1 → Next | Why? |
|---|---|---|---|---|
| 0 | ||||
| 0 | ||||
| 0 | ||||
| 0 | on 1 we reach the match state |
|||
| 1 | behaves like for future input (it holds a 1), but outputs 1 |
Common mistakes
Active recall
Recall What is a "state", in one line?
A finite label summarizing exactly the part of past input needed to decide future outputs & transitions.
Recall Why can Mealy machines often use fewer states than Moore?
Because Mealy attaches the output to transitions, so it doesn't need a separate state just to display an output.
Recall After detecting
1011 with overlap, why go to not ?
The trailing 1 is a valid prefix of a new 1011; going to would discard it and miss overlapping matches.
Recall (Feynman) Explain state design to a 12-year-old.
Imagine a lock that opens only if you press 1, 0, 1, 1 in order. The lock can't remember every button you ever pressed — that's too much. Instead it keeps a tiny sticky note saying "how far along the secret code am I?" Each note ("nothing yet", "got the 1", "got 1-0", "got 1-0-1") is a state. When a button is pressed, the lock updates the sticky note and, if it just finished the code, it pops open. A state diagram is just a map of all the sticky notes with arrows showing which button leads where.
Connections
- Finite State Machines — the abstract model behind these diagrams
- Flip-Flops and Latches — the physical memory that stores the state bits
- State Assignment and Reduction — choosing codes & merging equivalent states
- Excitation Tables and Next-State Equations — steps 6+ of the recipe
- Sequence Detectors — the canonical application
- Combinational Circuits — contrast: no memory, no states
What summarizes the past in a sequential circuit?
In a Moore machine, output depends on what?
In a Mealy machine, output depends on what?
Where is the output written in a Mealy state diagram?
Where is the output written in a Moore state diagram?
Why does a sequence detector for '1011' with overlap return to the '1' state after a match?
List the 6 steps of state-machine design.
Why does Moore usually need ≥ as many states as Mealy?
What makes a state table 'complete'?
For '1011' Mealy detector, how many states are needed?
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, sequential circuit ka matlab hai ek aisa circuit jo past yaad rakhta hai. Lekin poora history yaad rakhna impossible hai — infinite memory chahiye. Isliye hum ek smart trick use karte hain: saari possible histories ko chhote-chhote labels me squeeze kar dete hain, jinko hum state kehte hain. Har state basically ek sticky note hai jo bolta hai "abhi tak main kitna aage pahunch gaya hoon". Yehi core idea hai.
State diagram ek map hai — circles matlab states, aur arrows matlab input aane par kahan jaana hai. State table wahi cheez table form me hai: rows = present state, columns = input, aur andar likha hai next state aur output. Dono same information, bas alag look.
Ek important cheez: Moore vs Mealy. Moore me output state ke andar likha jaata hai (circle me), matlab output sirf state pe depend karta hai. Mealy me output arrow pe likha jaata hai (X/Z form), matlab output state + current input dono pe depend karta hai. Isliye Mealy usually kam states me kaam kar leta hai, par Moore glitch-free aur stable hota hai. Yaad rakho: "MOORE = Output On Resting spot, MEALY = output Meets you en-route."
Sabse badi galti jo students karte hain: 1011 detect karne ke baad wapas start state pe chale
jaana. Yeh galat hai jab overlapping allowed ho, kyunki 1011 ka last 1 naye pattern ka pehla
1 ban sakta hai. Isliye match ke baad pe jaana hai, pe nahi. Ye chota sa point exams me
bahut baar puchha jaata hai — dhyan rakhna!