skip to content

Why can no complete deterministic acceptor of badge frames exactly n symbols long use fewer than n+2 states?

level: seniorimportance: nice to knowfreq 26%

answer

  1. count what must be remembered
  2. one state per distinguishable prefix
  3. each prefix length needs its own
  4. over-long inputs share one class
  5. n+1 counting classes plus dead

basics

~20 s

Because the language has n+2 Myhill-Nerode classes: one per prefix length from 0 to n, plus one for everything already too long. A machine with fewer states would place two classes on one state and then give their separating suffix the same verdict, which is impossible.

solid answer

~50 s

The only memory a finite acceptor has is its current state, so count what it must remember. After reading `i` symbols with `i` at most `n`, the machine must still accept exactly the continuations of length `n - i`; two different prefix lengths therefore need different states, because the suffix that completes one over-runs the other. That is `n + 1` classes. Everything longer than `n` symbols is beyond rescue and forms one further class, giving `n + 2`. If a machine had fewer states, two strings from different classes would share a state and the machine would give their separating suffix the same verdict — but one extension is a valid frame and the other is not. No encoding trick avoids this, because the bound is about information that must survive between symbols, not about how a state is represented.

go deeper

for a junior

Recall that a finite acceptor's only memory is its current state, so anything it must count has to appear as distinct states.

for a middle

Produce the separating suffix for two prefix lengths and explain why that makes the two situations need different states.

for a senior

Use the bound to answer a real sizing question: show which situations a validator must tell apart before anyone argues about tables, encodings or gate count.

for a principal

Recognise when a lower bound is telling you the specification is wrong: if the required state count is unacceptable, the thing to renegotiate is the language, not the implementation.

A hardware engineer proposes a clever state encoding for a badge reader that validates fixed-width frames: records that are exactly `n` symbols long, no more and no less. The claim is that the counter can be compressed below the obvious size. The Myhill-Nerode argument settles it in one paragraph, and knowing how to run that argument is what this question probes. ## Counting what the machine must remember A deterministic finite acceptor has no tape, no stack and no counter beyond the state it currently occupies. So the question `how few states can this take?` becomes `how many situations must the machine be able to tell apart?` Two input strings `x` and `y` need different states whenever some suffix `w` completes one into a valid frame and the other into an invalid one. For frames of exactly `n` symbols: - Take `x` of length `i` and `y` of length `j`, both at most `n`, with `i` different from `j`. Append the suffix `w` of length `n - i`. Then `xw` has length exactly `n` and is accepted, while `yw` has length `j + n - i`, which is not `n`, and is rejected. So every pair of distinct lengths from `0` through `n` is distinguishable: **`n + 1` classes**. - Take any string longer than `n`. No suffix can shorten it, so every such string is rejected on every continuation. They are all equivalent to one another, and distinguishable from each of the classes above by the suffix that completes that class: **one further class**. Total: **`n + 2`** classes. ## From classes to a hard floor The step that makes this a lower bound rather than a construction is a pigeonhole argument. Suppose a machine had at most `n + 1` states. Two strings from different classes would then reach the same state. But once two strings are in the same state, the machine's behaviour on every continuation is identical — the state is all it has. The separating suffix would therefore receive one verdict, while the definition of the classes says one extension is a valid frame and the other is not. Contradiction. So `n + 2` is not a property of anyone's design. It is a property of the language, and the minimal machine achieves it exactly: | Class | Meaning | Accepting | |---|---|---| | `q0` through `qn` | exactly `i` symbols read so far, `i` from `0` to `n` | only `qn` | | `dead` | more than `n` symbols read | no | With `n = 2` that is four states: seen none, seen one, seen two and accepting, and over-long. Add one symbol to the frame width and the machine grows by exactly one state. ## Why no encoding trick helps Candidates often answer that packing more information per state would reduce the count. That confuses the **representation** of a state with the **number of distinguishable situations**. A state can be a register value, a wide bit vector or a table row; the bound counts how many behaviourally different situations the machine must keep apart, and the representation does not change that count. If a design claims fewer states, either the language is not what you thought it was — for example the frame width is bounded differently, or trailing symbols are tolerated — or it is not a complete deterministic acceptor. One honest refinement: the `+2` includes the dead state, which exists because the transition function is total. A formulation that allows undefined transitions can leave the dead class implicit and quote `n + 1`. That is a bookkeeping difference in how a rejected run is reported, not a saving in what has to be remembered — the machine still has to tell `n + 1` prefix situations apart. ## Using the bound at work The argument generalises to any `how small can this validator be?` question. Name the situations that a future input can tell apart, show the suffix that tells each pair apart, and you have both the floor and, usually, the design of the minimal machine at the same time. It is also the standard way to show that a proposed state table is already as small as possible, which is the constructive counterpart of running refinement and hoping the count drops.

  • Where exactly does the +2 in n+2 come from?
    One of the two is the dead class for inputs already longer than `n`, which no suffix can rescue. The other comes from counting prefix lengths inclusively: lengths `0` through `n` are `n + 1` classes, not `n`. Forgetting either is the usual off-by-one in this argument.
  • What changes if the acceptor may leave some transitions undefined?
    The floor becomes `n + 1`. A partial machine can simply have no transition once the frame is over-long, leaving the dead class implicit rather than materialised as a state. The number of prefix situations it must distinguish is unchanged, so nothing about the underlying memory requirement improves.
  • How would you use this argument to show a state table is already minimal?
    Exhibit one input string per state and a suffix separating each pair, which proves the machine has at least that many classes. Since a machine can never have fewer states than classes, and yours has exactly that many, it is minimal — no refinement run needed.

A stamp machine that must punch a card at exactly the tenth swipe has to know how many swipes it has seen; no clever ink saves it from keeping eleven distinct situations apart, plus one for cards already over-punched.

saying these in an interview costs you the question

  • Claims a denser state encoding beats the counting bound
  • Counts only the start state and the accepting state
  • Forgets the class for inputs already longer than n
  • Counts prefix lengths as n rather than n+1
  • Merges two prefix-length states because both are non-accepting