2.4Pumping lemma for regular languages
The idea
The pumping lemma says a long string in a regular language has a middle piece y that can be repeated or deleted without leaving the language.
Think of it like this: A DFA with p states must revisit a state when reading p symbols, so it can loop on that part any number of times.
Why it exists
It is the main tool for proving a language is not regular.
How it works
- Assume L is regular with pumping length p (the adversary picks p).
- You pick a string s ∈ L with |s| ≥ p.
- The adversary splits s = xyz with |xy| ≤ p and |y| ≥ 1.
- You pick i and show xyⁱz ∉ L. If you can beat every split, L is not regular.
Worked example: aⁿbⁿ
Take s = aᵖbᵖ. Since |xy| ≤ p, y consists only of a's. Pump up (i = 2): more a's than b's, so the string is not in L.
Now play with it
- →Pick aⁿbⁿ, move the sliders over every split and press "pump": always leaves L.
- →Switch to (ab)*: some split survives, because it IS regular.
Chosen string s ∈ L with |s| ≥ p: aaaabbbb (length 8)
The adversary splits s = x y z with |xy| ≤ p and |y| ≥ 1. Try splits:
x yⁱ z = aaaaaabbbb → NOT in L
No split survives. Whatever the adversary does, some pumped string leaves L, so L cannot satisfy the lemma: L is not regular.
Check yourself
The pumping lemma can be used to prove that a language is
Exam notes (the dense version)
If L is regular there is a p such that every s ∈ L with |s| ≥ p can be split s = xyz with |xy| ≤ p, |y| ≥ 1 and xyⁱz ∈ L for all i ≥ 0. Use it as a game to prove a language is not regular. It can never prove a language regular.
Previous year questions: Regular Expressions & Regular Languages (14)
PYQs are grouped by topic, so this is the full set for Regular Expressions & Regular Languages; try the ones that match this subtopic. Open all 14 on the topic page.