Pumping lemma for regular languages

1. State the pigeonhole principle.
   Stuck? Peek at 0.2.4 Pigeonhole principle

   • n + 1 objects in n boxes ⇒ some box has ≥ 2.
   • N objects in k boxes ⇒ some box has ≥ ⌈N/k⌉. To force m in a box: (m−1)k + 1 objects.
   • Machine with n modes, input length ≥ n ⇒ some mode repeats ⇒ a loop in the input.

   Read lesson 0.2.4

2. What is the contrapositive of P ⇒ Q?
   Stuck? Peek at 0.2.3 Proof techniques

   • P ⇒ Q false only when P true, Q false. Contrapositive ¬Q ⇒ ¬P ≡ original. Converse/inverse are NOT.
   • Contradiction: assume ¬S, derive the impossible. Used for “no machine can…” proofs.
   • Induction: base S(n₀) + step S(k) ⇒ S(k+1). Strong induction assumes all S(≤k).
   • One counterexample kills a “for all”. Examples never prove it.

   Read lesson 0.2.3

3. Is the emptiness question for DFAs answerable by an algorithm?
   Stuck? Peek at 2.4.2 Algorithms for regular languages

   • Membership: run. Emptiness: reachable F? Finiteness: trim + cycle (or lengths n..2n−1). Universality: complement + emptiness. Equivalence: minimize & compare, or symmetric difference empty. Containment: L₁ ∩ L̅₂ = ∅.
   • All these have always-terminating algorithms for regular languages.

   Read lesson 2.4.2

Your friend still insists their finite-mode machine checks balanced brackets. Myhill–Nerode can refute it, but GATE and most textbooks use a different weapon: the pumping lemma. It says every long enough string in a regular language has a section that can be repeated (“pumped”) any number of times without leaving the language. Find a language where pumping always breaks something — and you’ve proven no DFA exists.

A DFA has 4 states and accepts the string aaaaabbbbb. Why must there be a loop somewhere in the first 4 symbols of the run?

Prediction check

Reading 4 symbols gives 5 moments but only 4 states — pigeonhole (0.2.4) forces a repeated state within the first 4 symbols. The input between the two visits is a loop. Since the first 4 symbols are all a’s, the loop reads only a’s.

The lemma

Proof: let p = number of states of a DFA for L. Reading the first p symbols of w visits p + 1 moments, so some state repeats within them. x = input before the first visit, y = input between visits (non-empty, a loop), z = the rest. Repeating the loop i times (or skipping it, i = 0) ends in the same state ⇒ still accepted. ∎

Using it to prove NON-regularity (contrapositive game)

The lemma has the shape “regular ⇒ property”. Its contrapositive: “property fails ⇒ not regular”. Play it as a game against an opponent who claims L is regular:

1. Opponent picks p (you don’t know it — work with the symbol p).
2. You pick a string w ∈ L with |w| ≥ p (choose cleverly).
3. Opponent picks any split xyz with |xy| ≤ p, |y| ≥ 1.
4. You pick i such that xyⁱz ∉ L — for every possible split.

If you can always win, L is not regular (proof by contradiction, 0.2.3).

Classic: aⁿbⁿ

Pick w = aᵖbᵖ. Since |xy| ≤ p, x and y lie inside the a’s, so y = aᵏ with k ≥ 1. Pump i = 2: aᵖ⁺ᵏbᵖ ∉ L. Every split loses ⇒ not regular. ∎

Choosing w and i

• Put the “tension” within the first p symbols so |xy| ≤ p pins y down (aᵖbᵖ, not abab…).
• i = 0 (pump down) is often handy: removes symbols.
• For lengths: {a^{n²}} — pick a^{p²}; pumping once adds k ≤ p symbols: p² < p² + k ≤ p² + p < (p+1)², not a square.
• Primes {aᵖ : p prime}: pick a prime q ≥ p + 2, pump i = q − k… length becomes q + (i−1)k; with i = q + 1 length = q(1 + k), not prime.

The lemma is not a test for regularity

Putting it together

• Every long string of a regular language has an early loop y that can be pumped (pigeonhole).
• To prove non-regularity: pick w and i that beat every split with |xy| ≤ p, |y| ≥ 1.
• Passing the pumping test proves nothing.

w = aᵖ bᵖ ,  |xy| ≤ p  forces y inside the a-block

  a a a a a a a a | b b b b b b b b
  └x┘└─y─┘└─────── z ──────────────┘
       loop
 pump i=2:  a a a a a a a a a a a | b b b b b b b b   → more a's than b's ∉ L
 pump i=0:  a a a a a | b b b b b b b b               → fewer a's        ∉ L

DFA view: the run on the first p symbols repeats a state ↻ = y

We now have three ways to prove non-regularity: Myhill–Nerode, closure tricks, and pumping. The next lesson trains the fast intuition GATE needs: deciding “regular or not?” in seconds, by asking whether the language needs unbounded memory.

1. MCQ

   In the pumping lemma, which condition is NOT part of the statement?

   1. |xy| ≤ p
   2. |y| ≥ 1
   3. |x| ≥ 1
   4. xyⁱz ∈ L for all i ≥ 0
2. MCQ

   A language L satisfies the pumping conditions. Then:

   1. L is regular
   2. L is not regular
   3. nothing can be concluded about regularity
   4. L is finite
3. MSQ

   Which are valid choices when proving {aⁿbⁿ} non-regular?

   1. w = aᵖbᵖ
   2. w = (ab)ᵖ
   3. i = 0
   4. i = 2
4. NAT

   A DFA for L has 7 states. What pumping length p can we use?

   Write your answer before opening the key.

• pumping lemma (regular)
• pumping length p
• split w = xyz
• pumping up / down (i ≥ 2 / i = 0)
• adversary game

1. Three conditions of the regular pumping lemma?
   Reveal answer

   |xy| ≤ p, |y| ≥ 1, xyⁱz ∈ L for all i ≥ 0.
2. Does satisfying the pumping lemma prove regularity?
   Reveal answer

   No — it is necessary, not sufficient.
3. Who picks what in the pumping game?
   Reveal answer

   Opponent: p and the split. You: w and i.
4. Pumping length from a DFA?
   Reveal answer

   Its number of states.