skip to content

For inputs of opening brackets then closing brackets with strictly more opens than closes, why must a pumping argument use i = 0?

level: seniorimportance: should knowfreq 36%

answer

  1. for every i, zero included
  2. ask where the language has slack
  3. adding opens keeps the inequality
  4. deleting drops opens to at most p
  5. witness p + 1 opens, p closes

basics

~20 s

Repetition only adds opening brackets, which keeps the strict inequality true, so pumping upward never leaves the language. Deleting the block instead drops the opening count to the closing count or below, breaking the strict inequality and giving the contradiction.

solid answer

~50 s

The lemma says `x y^i z` stays in the language for **every** `i >= 0`, and `i = 0` is one of them — that case deletes the block. Take the witness with `p + 1` opens followed by `p` closes, where `p` is the pumping length. The prefix bound `|xy| <= p` puts the pumped block `y` inside the opening run, with `k = |y| >= 1`. Pumping up gives `p + 1 + k(i - 1)` opens against `p` closes, which still satisfies "strictly more opens", so no upward repetition contradicts anything. Taking `i = 0` leaves `p + 1 - k` opens against `p` closes, and since `k >= 1` that is at most `p` — the strict inequality fails, so the string is outside the language while the lemma insists it is inside. Reaching for `i = 2` reflexively is how candidates get stuck here.

go deeper

for a junior

Note that the lemma allows the repetition count to be zero, which means deleting the block, and that deletion is sometimes the only case that breaks a language.

for a middle

Explain the arithmetic on both sides: adding opens preserves a strictly-more-opens rule, while removing at least one drops the count to the closing count or below.

for a senior

Show the method behind it: identify which direction the language has slack in, build the witness so the adversary must disturb the counter you intend to attack, then pump against the slack.

for a principal

Take the lesson into specification review. A rule expressed as an unbounded comparison of two counts has quietly chosen the validator class for everyone downstream.

## The language and the witness The rule under test accepts a run of opening brackets followed by a run of closing brackets, and requires **strictly more** opens than closes — a plausible shape for a format that permits trailing structure to be closed later. Assume for contradiction that a finite-state recogniser accepts exactly these strings, and let `p` be its pumping length. Choose the witness `s` with `p + 1` opening brackets followed by `p` closing brackets. It is in the language, because `p + 1 > p`, and `|s| = 2p + 1 >= p`, so the lemma applies. The adversary now splits `s = x y z` with `|y| >= 1` and `|xy| <= p`. The first `p` symbols are all opening brackets, so `y` is a non-empty run of opens; write `k = |y|`, with `1 <= k <= p`. ## Why the reflexive upward pump fails Pumping to `i` yields `p + 1 + (i - 1) * k` opening brackets and, untouched, `p` closing brackets. | `i` | opens | closes | strictly more opens? | |---|---|---|---| | 0 | `p + 1 - k` | `p` | no, since `k >= 1` makes this at most `p` | | 1 | `p + 1` | `p` | yes — this is the original witness | | 2 | `p + 1 + k` | `p` | yes | | 3 | `p + 1 + 2k` | `p` | yes | Every upward repetition adds opens to a string that already had more opens than closes, so it lands **inside** the language. There is nothing wrong with the witness and nothing wrong with the lemma: this language is simply closed under adding opens to the front. Only `i = 0` moves against the inequality, and it wins immediately — deleting a block of at least one opening bracket leaves at most `p` opens against exactly `p` closes, so "strictly more" fails and the pumped string is outside the language. The lemma demanded it be inside. Contradiction, and the language is not regular. ## The general shape: pump against the slack The useful habit is to ask which direction the language has **slack** in, and pump the other way. 1. If a language demands an exact match between two counts, both directions break it, and `i = 2` is the conventional choice. 2. If a language demands one count exceed another, upward pumping on the larger side has unlimited slack; the only pressure is downward. 3. If a language constrains a length property rather than a comparison of counts, neither direction is automatic and the choice depends on where the property's next admissible value sits. Deleting the block is a legitimate move precisely because clause 3 of the lemma quantifies over all `i >= 0` and does not exclude zero. Candidates who memorised the lemma as "repeat the middle part" lose this case entirely, conclude the language passes, and then either give up or, worse, claim the language is regular — which does not follow from a failed refutation in either direction. ## Choosing the side the block lands on Notice the second reason the witness is built with the opens first. The prefix bound only restricts the first `p` symbols, so putting the run you want to attack at the front forces the adversary's block into it. Had the witness been written with closes first, the block would sit in the closing run and the pumped string would break a different clause — or none, if the language happens to have slack there too. Designing the witness means choosing **which counter the adversary is forced to disturb**, and only then choosing the direction that hurts. ## What a strong answer sounds like A strong answer names the quantifier ("for every `i >= 0`, including zero"), states the arithmetic on both sides (`p + 1 - k` against `p`, with `k >= 1`), and says explicitly why the upward pump is not merely inconvenient but genuinely inside the language. A weak answer asserts that the string "stops being balanced" without tracking the counts, which is not even the property this language asks for — nothing here demands balance, only a strict inequality between two counts.

  • How do you decide, in general, whether to pump up or down?
    Ask which direction the language has slack in. A language demanding equality between two counts breaks in both directions, so repetition is conventional. A language demanding one count strictly exceed another absorbs unlimited growth on the larger side, so only deletion applies pressure. Work out what the pumped string's counts become before committing to a value of `i`.
  • Does the deleted block have to come from the first run for this argument to work?
    For this witness it does, and the prefix bound guarantees it. The clause `|xy| <= p` restricts the block to the first `p` symbols, which are all opening brackets, so the adversary cannot place it among the closes. That is why the witness is written with the run you want disturbed at the front.
  • If neither pumping up nor pumping down leaves the language, what have you shown?
    Nothing about regularity. A failed refutation means this witness does not work; another witness may, or the language may genuinely be regular. The pumping property is a consequence of regularity, not a test for it, so only exhibiting a machine or a pattern settles the positive direction.

saying these in an interview costs you the question

  • Believes pumping means repeating and never deleting
  • Claims i equal to 0 is outside the lemma's range
  • Says adding opening brackets breaks a strictly-more-opens rule
  • Concludes the language is regular after the upward pump survives
  • Ignores that the prefix bound decides which run is disturbed