Intuition The one core ideaA machine that remembers only ever lives in one of finitely many "situations" (states); two situations are the same if the outside world can never tell them apart no matter what buttons it presses. State minimization is just the hunt for these look-alike situations so we can glue them together and build a smaller, cheaper machine.
This page assumes nothing . Every arrow, letter, and squiggle used in the parent note is unpacked here, in the order a beginner needs them. If a symbol confused you up there, it is defined here first.
Everything about minimization lives inside a state diagram : bubbles connected by labelled arrows. Before any algebra, burn this picture into your mind.
Each circle = a state — one distinct "situation" the machine can be sitting in.
Each arrow = a transition — "if this input arrives, jump to that circle."
The label on an arrow = the input that triggers the jump.
The number written near/in a circle or on the arrow = the output .
Every symbol below is just a piece of this drawing given a name.
A state is one of the finitely many distinct configurations a machine's memory can hold. In the drawing it is one circle .
Intuition Why do we even need states?A pocket calculator with no memory reacts to a button the same way forever. A machine with memory reacts differently depending on what happened before . That "what happened before" is compressed into the current state — a single circle. The circle is the machine's entire recollection of the past.
Symbols the parent uses for individual states: A , B , C , D p , q names of circles — nothing more.
Related building block: Flip-Flops are the physical hardware that actually stores which state you are in. See §7.
x input is a signal fed to the machine from outside, at each tick of time. The parent uses x ∈ { 0 , 1 } label written on an arrow .
An output is what the machine emits in response. In the parent's tables it is the last column (a 0 1 number attached to a circle or an arrow .
The set notation x ∈ { 0 , 1 } x { } mean "the collection of," and ∈ entire meaning — no calculus, no hidden depth.
Worked example Reading one rowThe parent's row A | B | C | 0 says: "When in circle A: input 0 sends me to B, input 1 sends me to C, and while sitting in A I output 0."
This distinction decides how we start the whole algorithm, so it must be crystal clear.
Definition Moore vs Mealy
Moore machine: the output depends only on the current state . One output number per circle . (This is the parent's worked examples — the "Output" column.)Mealy machine: the output depends on state AND input . One output per arrow , so a state has a whole row of outputs (one for each possible input).
Intuition Why this matters for minimizationMinimization begins by grouping states with the "same output." For Moore that is one value to compare; for Mealy it is an entire row of values. Get this wrong and your very first grouping is wrong. Deeper contrast lives in Mealy vs Moore Machines .
The whole framework is a Finite State Machine — "finite" because there is a limited number of circles.
Definition Next-state functionδ δ ( p , x ) "the next state you reach from state p x It is nothing but the arrow in the picture, turned into a formula. The Greek letter δ delta ) is just a traditional name — think "d for destination."
Why introduce a symbol at all when we have arrows? Because the algorithm must talk about "the next state of p q Saying that in pictures every time is exhausting; δ That is the only reason the symbol exists — compression of the arrow.
δ Why it feels right: the fancy Greek letter looks scary. Why wrong: δ lookup , not a computation — it just reads off which circle the arrow points to. Fix: read δ ( p , x ) p x
We now build the single most important idea: two circles being indistinguishable .
p ≡ q p ≡ q "p q ) means: for every possible input string, starting in p same output stream as starting in q ≡ =
Intuition The twin-robots pictureTwo robots are twins if no button-sequence you press ever makes them beep differently. You could swap one for the other and no observer could catch you. Twins are wasteful — keep one, discard the other.
What kind of relation is ≡ The parent calls it an equivalence relation . That phrase means it obeys three natural rules:
Definition The three laws of an equivalence relation
Reflexive: p ≡ p Symmetric: if p ≡ q q ≡ p Transitive: if p ≡ q q ≡ r p ≡ r
Why do we care about these three laws? Because they guarantee the states fall into clean, non-overlapping groups. No state can be "a little bit in two groups." Those groups are called equivalence classes , and each class collapses to one circle in the minimized machine. This clean-grouping guarantee is what makes minimization possible , and it is formalised by the Myhill–Nerode Theorem .
Definition Partition and blockA partition of the states is a way of chopping them into groups so that every state is in exactly one group. Each group is called a block . The parent writes a partition like { A , B , C } { D } A , B , C D
P k P k k k
P 0 current output (zero steps of future).P 1 one input.…and so on, refining as k
Definition The refinement symbol⪰ P 0 ⪰ P 1 ⪰ ⋯ ⪰ "is at least as coarse as." Coarse = big blocks (few groups); fine = small blocks (many groups). Each step can only split blocks, never merge them, so partitions get finer (or stay the same). When two consecutive ones are identical, P k + 1 = P k
Intuition Why refinement must stopThere are only finitely many circles. Every step either breaks a block into smaller pieces or changes nothing. You cannot break finite things forever — eventually a full pass changes nothing, and that frozen partition is the set of true twin-groups.
The number this whole exercise minimizes is the state count N
⌈ log 2 N ⌉
log 2 N N "how many bits to label N With b 2 b b 2 b ≥ N The brackets ⌈ ⌉ ceiling — "round up to the next whole number," because you cannot buy 2.3 flip-flops.
Worked example Why cutting states saves hardwareN = 4 ⇒ ⌈ log 2 4 ⌉ = 2 N = 2 ⇒ ⌈ log 2 2 ⌉ = 1 a whole flip-flop saved.
But 4 → 3 ⌈ log 2 3 ⌉ = 2 always drop a flip-flop, though the logic still shrinks.
Each surviving block is given a bit-pattern by State Assignment (Encoding) , and the resulting next-state/output logic is then simplified with Karnaugh Maps . So minimization sits upstream of both.
Finite State Machine circles and arrows
Moore vs Mealy output placement
Transition function delta lookup
Equivalent states p equiv q
Equivalence relation three laws
Refinement P0 to P1 to stable
Flip-Flop count ceil log2 N
State Assignment then Karnaugh Maps
What does a single circle in a state diagram represent? One state — one complete "situation" the machine's memory can hold.
What does x ∈ { 0 , 1 } x belongs to the set whose members are 0 and 1 — i.e. the input is either 0 or 1.
Where does the output live in a Moore machine vs a Mealy machine? Moore: one value per state (circle). Mealy: one value per input, so a whole output row per state (arrows).
Read δ ( C , 1 ) = A From state C 1 A
What does p ≡ q ≡ = For every input string p q ≡
Name the three laws that make ≡ Reflexive (p ≡ p p ≡ q ⇒ q ≡ p p ≡ q , q ≡ r ⇒ p ≡ r
What is a block of a partition? One group of states in a chopping-up where every state lands in exactly one group.
What does the subscript k P k How many steps of future input have been used to distinguish states so far.
What does P 0 ⪰ P 1 P 0 P 1
Compute the flip-flops needed for 5 states. ⌈ log 2 5 ⌉ = 3
