A payload is valid only when its cell count is a perfect square. How does a pumping argument rule out finite-state validation?

## A length rule, not a counting rule The validator here is not comparing two counts inside the input; it is testing a property of the input's **length** alone. Suppose a stream of fixed-size cells is valid only when the number of cells is a perfect square — a grid payload, say, that must be square. The question is whether a recogniser with finitely many states and no counter can decide this as the cells go past. Assume it can, and let `p >= 1` be the pumping length of the language of valid payloads. Choose the witness of exactly `p * p` cells: it is in the language, and its length `p * p` is at least `p`, so the lemma applies. ## The prefix bound as a size bound In the balanced-bracket argument, the clause `|xy| <= p` matters because it says **where** the pumped block sits. Here it matters because it says **how large** the block can be. Every legal split has `1 <= k <= p`, writing `k` for the block's size. There is no case analysis worth doing: the input is a uniform run of cells, so all splits are interchangeable and only `k` matters. Pump once, taking `i = 2`, and the length becomes `p * p + k`. Two bounds sandwich it: 1. `p * p + k > p * p`, because `k >= 1`; 2. `p * p + k <= p * p + p < p * p + 2p + 1 = (p + 1) * (p + 1)`, because `k <= p` and `p >= 1`. So the pumped length lies strictly between `p * p` and `(p + 1) * (p + 1)`, two consecutive squares, and is therefore not a square. The payload is invalid, yet clause 3 of the lemma promised the recogniser accepts it. Contradiction; no finite-state recogniser decides the square-length rule. ## Why the gap argument is the general form The reason this works is that consecutive squares drift apart: the gap between `n * n` and `(n + 1) * (n + 1)` is `2n + 1`, which grows without bound, while the pump step is stuck at most `p`. Any length rule whose admissible values eventually spread further apart than the pumping length falls to the same argument — a bounded stride cannot keep landing on targets that keep moving apart. | rule on the length | consecutive gap | finite-state checkable | |---|---|---| | length is even | 2, constant | yes — one bit of state | | length leaves remainder 3 on division by 7 | 7, constant | yes — a modular counter with 7 states | | length is a perfect square | grows as `2n + 1` | no — pump step is bounded, gaps are not | | length is a power of two | grows, doubling | no — same argument, different arithmetic | The first two rows are the contrast that makes the third honest. Counting is not what defeats a finite machine; **unbounded** counting is. A machine can count as far as it likes modulo a fixed number, because remainders wrap into finitely many states. ## Doing the arithmetic out loud Interviewers watching this answer are checking the inequality chain, not the vocabulary. The two bounds must both be stated, and the second must use `k <= p`: without the prefix bound the block could be arbitrarily large and the pumped length might land exactly on the next square, leaving no contradiction. That dependency is the point of the whole case — it shows the candidate knows which clause of the lemma is doing the work, rather than reciting a pattern learned from the bracket example. It is also worth saying which pump direction was used and why `i = 2` suffices: any `i > 1` works by the same chain with `(i - 1) * k` in place of `k`, as long as the arithmetic is redone, while `i = 0` also works here since `p * p - k` sits strictly between `(p - 1) * (p - 1)` and `p * p` for `p >= 2`. Unlike the strict-inequality language, this one has slack in neither direction.