How does partition refinement collapse a six-state badge acceptor into the smallest deterministic machine accepting the same sequences?

middleshould knowfreq 48%

answer

start from accept versus reject
split blocks, never merge them
compare where each letter leads
run until a pass changes nothing
each final block is one state

basics

~20 s

Start with two blocks, accepting states and non-accepting states, then repeatedly split any block whose members send some input letter into different blocks. When no split applies, each remaining block becomes one state of the minimal machine.

solid answer

~50 s

Refinement works top-down on groups rather than pair by pair. The initial partition has two blocks: accepting and non-accepting states, the split the empty suffix forces. Then you compute, for every state in a block, which block each input letter leads to; members whose block signatures differ cannot be equivalent, so the block splits along those signatures. Repeat until a full pass splits nothing. Each surviving block is one state of the minimal acceptor, its transitions inherited from any member, the start block is the start state, and blocks of accepting states accept. Blocks only ever subdivide and there are at most as many as there are states, so the loop terminates. Hopcroft partition refinement does the same work in O(n log n) for a fixed alphabet, where n is the number of states, against O(n^2) per the naive pass-based version.

Refinement works top-down on groups rather than pair by pair. The initial partition has two blocks: accepting and non-accepting states, the split the empty suffix forces. Then you compute, for every state in a block, which block each input letter leads to; members whose block signatures differ cannot be equivalent, so the block splits along those signatures. Repeat until a full pass splits nothing. Each surviving block is one state of the minimal acceptor, its transitions inherited from any member, the start block is the start state, and blocks of accepting states accept. Blocks only ever subdivide and there are at most as many as there are states, so the loop terminates. `Hopcroft partition refinement` does the same work in `O(n log n)` for a fixed alphabet, where `n` is the number of states, against `O(n^2)` per the naive pass-based version.

code

pseudocode · 18 lines

pseudocode

partition = { set of accepting states, set of non-accepting states }

repeat
  progress = false
  for each block B in partition
    for each state s in B
      signature(s) = list over letters a of blockIndex(delta(s, a))
    groups = members of B grouped by equal signature
    if groups has more than one group
      replace B in partition by the groups
      progress = true
until progress is false

minimal machine:
  one state per block
  start state  = block containing the original start state
  accepting    = blocks whose members are accepting
  transition   = blockIndex(delta(any member, a))

go deeper

for a junior

Remember the shape: accepting states start apart from the rest, blocks only get smaller, and the number of blocks left at the end is the number of states you need.

for a middle

Walk the rounds out loud on a small machine, stating the signature that forces each split and why a pass with no split proves the partition is stable.

for a senior

Be ready to say what this costs on a machine large enough to matter and when you would instead compute pairwise witnesses, because a witness string is the artefact that settles an argument between two teams.

for a principal

Decide where minimization belongs in the toolchain — a check in a verification step that derives the canonical machine, rather than a transformation applied to the source that engineers read and debug.

The invariant the loop maintains

The partition holds blocks of states not yet proven different. It starts as coarse as it can honestly be — accepting states in one block, non-accepting in the other, which is the split the empty suffix already forces — and it only ever gets finer. The loop is:

For each state, form its signature: the block that each input letter leads into.
Within a block, group the members by signature.
If a block yields more than one group, replace it by those groups.
Repeat until a complete pass splits nothing.

Because blocks only subdivide and never re-merge, and a machine with n states admits at most n blocks, the process terminates. At the fixed point, two states share a block exactly when no suffix separates them.

Worked example: six states down to three

The door controller accepts badge sequences containing at least two valid scans, over letters v (valid) and x (rejected).

State	Accepting	on `v`	on `x`
`A` start, no valid scan	no	`B`	`D`
`D` no valid scan, invalid logged	no	`C`	`D`
`B` one valid scan	no	`E`	`B`
`C` one valid scan, other path	no	`F`	`C`
`E` unlocked	yes	`E`	`E`
`F` unlocked, other path	yes	`F`	`F`

Round	Partition	What split, and why
0	`{A,B,C,D}` / `{E,F}`	accepting against non-accepting — the empty suffix
1	`{A,D}` / `{B,C}` / `{E,F}`	on `v`, `A` and `D` stay inside block 1 while `B` and `C` leave for block 2
2	unchanged	every block now sends each letter into a single block

On x in round 1 nothing extra splits: A, D, B and C all stay inside block 1. The result is three states — still need two scans, still need one, unlocked — with {A,D} as the start state and {E,F} accepting. Six states of firmware, three states of language.

Why the signature comparison is enough

It looks like a shortcut: a single letter is compared, not every suffix. The reason it works is that the loop runs to a fixed point. If some suffix a followed by w separates two states, then w separates their a-successors, so those successors are eventually placed in different blocks, and the next pass separates the originals. Each round effectively extends the length of witness considered by one letter, and the fixed point covers all lengths.

Cost, and what `n` is

Naive pass-based refinement costs O(n^2) work for a fixed alphabet, where n counts states: each pass touches every state and there can be up to n passes.
Hopcroft partition refinement schedules splits so that the smaller half of every split is processed, bringing it to O(n log n) for a fixed alphabet. Multiply by alphabet size in both cases.
Applying the pairwise marking method instead costs O(n^2) pairs, but it hands you an explicit witness string per pair, which is more useful in a disagreement between teams.

Where candidates go wrong

Starting from one block. If accepting status is not separated first and the signature ignores it, the loop can happily leave an accepting and a non-accepting state together forever.
Stopping after one pass. Round 1 above created the blocks that round 2 has to re-examine; only a pass that splits nothing proves stability.
Trying to merge. The algorithm is monotone in one direction. A block split in round 1 is never rejoined, which is what makes termination obvious.
Reading the block count as anything but state count. Three blocks means three states, not three accepted strings.
Forgetting to trim first. Refinement classifies states; it does not delete states that no input can reach, and those states survive into the result as blocks of their own.

Distinguishability says which states may be merged. Partition refinement is how you compute that relation for a whole machine at once, and it is what an interviewer means when they ask you to minimize a controller on a whiteboard. ## The invariant the loop maintains The partition holds blocks of states **not yet proven different**. It starts as coarse as it can honestly be — accepting states in one block, non-accepting in the other, which is the split the empty suffix already forces — and it only ever gets finer. The loop is: 1. For each state, form its **signature**: the block that each input letter leads into. 2. Within a block, group the members by signature. 3. If a block yields more than one group, replace it by those groups. 4. Repeat until a complete pass splits nothing. Because blocks only subdivide and never re-merge, and a machine with `n` states admits at most `n` blocks, the process terminates. At the fixed point, two states share a block exactly when no suffix separates them. ## Worked example: six states down to three The door controller accepts badge sequences containing at least two valid scans, over letters `v` (valid) and `x` (rejected). | State | Accepting | on `v` | on `x` | |---|---|---|---| | `A` start, no valid scan | no | `B` | `D` | | `D` no valid scan, invalid logged | no | `C` | `D` | | `B` one valid scan | no | `E` | `B` | | `C` one valid scan, other path | no | `F` | `C` | | `E` unlocked | yes | `E` | `E` | | `F` unlocked, other path | yes | `F` | `F` | | Round | Partition | What split, and why | |---|---|---| | 0 | `{A,B,C,D}` / `{E,F}` | accepting against non-accepting — the empty suffix | | 1 | `{A,D}` / `{B,C}` / `{E,F}` | on `v`, `A` and `D` stay inside block 1 while `B` and `C` leave for block 2 | | 2 | unchanged | every block now sends each letter into a single block | On `x` in round 1 nothing extra splits: `A`, `D`, `B` and `C` all stay inside block 1. The result is three states — still need two scans, still need one, unlocked — with `{A,D}` as the start state and `{E,F}` accepting. Six states of firmware, three states of language. ## Why the signature comparison is enough It looks like a shortcut: a single letter is compared, not every suffix. The reason it works is that the loop runs to a fixed point. If some suffix `a` followed by `w` separates two states, then `w` separates their `a`-successors, so those successors are eventually placed in different blocks, and the next pass separates the originals. Each round effectively extends the length of witness considered by one letter, and the fixed point covers all lengths. ## Cost, and what `n` is - Naive pass-based refinement costs `O(n^2)` work for a fixed alphabet, where `n` counts states: each pass touches every state and there can be up to `n` passes. - `Hopcroft partition refinement` schedules splits so that the smaller half of every split is processed, bringing it to `O(n log n)` for a fixed alphabet. Multiply by alphabet size in both cases. - Applying the pairwise marking method instead costs `O(n^2)` pairs, but it hands you an explicit witness string per pair, which is more useful in a disagreement between teams. ## Where candidates go wrong - **Starting from one block.** If accepting status is not separated first and the signature ignores it, the loop can happily leave an accepting and a non-accepting state together forever. - **Stopping after one pass.** Round 1 above created the blocks that round 2 has to re-examine; only a pass that splits nothing proves stability. - **Trying to merge.** The algorithm is monotone in one direction. A block split in round 1 is never rejoined, which is what makes termination obvious. - **Reading the block count as anything but state count.** Three blocks means three states, not three accepted strings. - **Forgetting to trim first.** Refinement classifies states; it does not delete states that no input can reach, and those states survive into the result as blocks of their own.

What does Hopcroft partition refinement cost, and what is n counting?
`O(n log n)` for a fixed alphabet, with `n` the number of states; multiply by alphabet size in general. It achieves this by always processing the smaller side of each split, so each state appears in a processed set at most a logarithmic number of times. The straightforward pass-based version is `O(n^2)` because it can need one pass per state.
Why does the algorithm split blocks instead of merging states pairwise?
Splitting keeps a clean invariant: a block holds states not yet proven different, so nothing needs undoing. Blocks only subdivide and there are at most as many blocks as states, which makes termination immediate. Pairwise merging would have to re-check earlier merges each time new evidence arrived.
Why is comparing a single letter per round enough to capture all suffixes?
Because the loop runs to a fixed point. If the suffix `a` then `w` separates two states, `w` separates their `a`-successors, so those successors land in different blocks first and the next pass separates the originals. Each round covers witnesses one letter longer than the last.

saying these in an interview costs you the question

Refines by transitions without first separating accepting states
Stops after one pass instead of reaching a fixed point
Thinks refinement can rejoin blocks it split earlier
Declares two states equivalent after checking one letter alone
Reads the final block count as a count of accepted strings

How does partition refinement collapse a six-state badge acceptor into the smallest deterministic machine accepting the same sequences?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The invariant the loop maintains

Worked example: six states down to three

Why the signature comparison is enough

Cost, and what n is

Where candidates go wrong

▾common follow-ups3 questions

▾red flags5 flags

The invariant the loop maintains

Worked example: six states down to three

Why the signature comparison is enough

Cost, and what n is

Where candidates go wrong

answer

go deeper

Cost, and what `n` is

Cost, and what `n` is