skip to content

A non-regularity proof picks a convenient split of its witness string and pumps that. Why is the proof invalid?

level: middleimportance: should knowfreq 46%

answer

  1. quantifier order decides who moves
  2. adversary hands you p
  3. you choose witness and i
  4. the split is never yours
  5. engineer a one-case witness

basics

~20 s

Choosing the decomposition is the adversary's move, not the prover's. The lemma promises only that some legal split exists, so a valid argument must defeat every split allowed by the constraints; defeating one convenient split proves nothing.

solid answer

~50 s

Read the lemma as a game with a fixed move order. The adversary picks the pumping length `p`; you pick a witness string in the language with length at least `p`; the adversary picks `x`, `y`, `z` subject only to `|y| >= 1` and `|xy| <= p`; you pick the repetition count `i`. You control the witness and `i` — never the split. A proof that says "let `y` be the middle run" has stolen a move, and it collapses the moment the adversary chooses differently. The fix is not to enumerate splits harder but to choose a witness whose prefix makes all legal splits equivalent: when the first `p` symbols are a single repeated symbol, `|xy| <= p` leaves exactly one shape of `y`. A related stolen move is fixing `p` to a concrete number such as 5 — `p` is given to you, not chosen.

code

pseudocode · 11 lines
pseudocode
adversary chooses p >= 1                 # value never revealed to you
prover   chooses s in L with length(s) >= p      # written in terms of p
adversary chooses x, y, z with s = x + y + z
              and length(y) >= 1
              and length(x) + length(y) <= p
prover   chooses i >= 0                  # chosen after seeing the split

if (x + repeat(y, i) + z) not in L then
    prover wins: L is not regular
else
    adversary wins: this attempt proves nothing

go deeper

for a junior

Remember the shape of the obligation: you choose the string and how many times to repeat, someone else chooses the length bound and where the repeated block sits.

for a middle

Explain the quantifier alternation and why negating it turns the existential over decompositions into a universal, so every legal split must fail.

for a senior

Demonstrate it in review: point at the sentence that asserts the split, and show how to rewrite the witness so the prefix constraint derives the split instead.

for a principal

Treat it as a standard for how impossibility claims enter a design document. An argument nobody on the team can check is indistinguishable from an assertion.

## The lemma has a quantifier order, and the order is the whole rule Spelled out, the statement is: **for every** regular language `L` **there exists** a pumping length `p` such that **for every** string `s` in `L` with `|s| >= p` **there exists** a decomposition `s = x y z` with `|y| >= 1` and `|xy| <= p` such that **for every** `i >= 0`, `x y^i z` is in `L`. Each alternation of "for every" and "there exists" hands a move to a different player. To refute regularity you negate the statement, and negation flips every quantifier: you must show that **for every** `p`, **there exists** a string `s`, such that **for every** legal decomposition, **there exists** an `i` that leaves the language. That is why the existential over decompositions becomes a universal in your proof. The lemma guarantees only that *some* split works; it never says which. Picking the split yourself is not a shortcut — it proves a different, useless statement. ## Who moves when | move | whose | constraint | |---|---|---| | the pumping length `p` | adversary | some `p >= 1`, value unknown to you | | the witness `s` | you | `s` in `L`, `|s| >= p`, expressed in terms of `p` | | the split `x`, `y`, `z` | adversary | `|y| >= 1` and `|xy| <= p`, otherwise free | | the repetition count `i` | you | any `i >= 0`, chosen after seeing the split | Two consequences follow directly. First, your witness must be written **as a function of `p`**, because `p` is handed to you; a witness with concrete numbers in it only covers one value the adversary may never play. Second, your choice of `i` may depend on the split, which is a real freedom — nothing forces one value of `i` to work for all decompositions. ## The stolen-move family of broken proofs - **Choosing the split.** "Let `y` be the run of closing brackets" — the adversary simply plays a `y` inside the opening run instead, and the argument has nothing to say. - **Choosing `p`.** "Take `p = 5` and consider…" — the lemma says a pumping length exists, not that it is small. A refutation must survive every `p`. - **Choosing a witness that is too short.** The lemma constrains only strings of length at least `p`, so a witness shorter than `p` carries no obligation at all. - **Choosing a witness outside the language.** The pumping property applies to members of `L`. A non-member is unconstrained, and pumping it proves nothing. - **Testing only `i = 2`.** Some languages survive every upward pump and fail only at `i = 0`. One value of `i` failing to break the string is not the adversary's win either — you get to try another. ## Beating every split without enumerating them Good witnesses are engineered so the constraint `|xy| <= p` leaves the adversary no meaningful freedom. If the first `p` symbols of the witness are all the same symbol, then every legal `y` is a non-empty run of that one symbol, and a single case finishes the proof: the split is nominally free, but all free choices are interchangeable. This is the practical skill the lemma actually tests in an interview — not the recitation of the statement, but the ability to design a witness whose case analysis has one case. When a witness genuinely forces several shapes of `y`, the argument must handle each one, and each case needs its own `i`. A proof that handles two of three cases is not a proof; the adversary plays the third. ## How to spot it in review Read the proof looking only for the verbs. Every sentence of the form "let `y` be …", "assume the split puts …", or "take `p = …" is a stolen move unless it is immediately justified by the constraints — and the only legitimate justification has the shape "because `|xy| <= p` and the first `p` symbols are all opening brackets, `y` must be a run of opening brackets". That sentence derives the shape of `y` from the lemma rather than asserting it. If you cannot find such a derivation, the proof is asserting the adversary's move and is invalid regardless of whether its conclusion happens to be true.

  • Why must the witness be written in terms of p rather than as a concrete string?
    Because the adversary chooses `p` and never tells you its value. A concrete witness such as eight opens and eight closes only meets the lemma's obligation when `p` is at most sixteen; for a larger `p` the string is too short to constrain anything. Parameterising the witness by `p` makes the argument survive every value.
  • May different legal splits use different values of i?
    Yes, and that freedom is often needed. The negated statement requires, for each decomposition, the existence of some `i` that leaves the language — not one `i` that works uniformly. A case analysis that pumps up in one case and down in another is perfectly valid.

saying these in an interview costs you the question

  • Lets the prover choose the decomposition of the witness
  • Fixes the pumping length to a small concrete number
  • Picks a witness shorter than the pumping length
  • Pumps a string that is not in the language at all
  • Believes one convenient split failing settles the whole claim
  • Gives up when i equal to 2 keeps the string inside the language