4.6.7 · D5Theory of Computation
Question bank — Pumping lemma for regular languages — proof and using to show non-regularity
Before we start, the moving parts you will keep meeting:
- — the pumping length, a fixed but unknown number the adversary hands you.
- — your chosen string cut into three pieces by the adversary.
- — the length of (how many symbols it has).
- The three conditions: ==, , and for all == (here is the pumping exponent — how many times you repeat the loop ).
The picture below is the whole engine in one glance — refer back to it while answering.
True or false — justify
The pumping lemma can prove a language is regular.
False — it is a necessary condition only. It can only prove NON-regularity; to prove regularity you build a DFA/regex or use Myhill–Nerode.
If a language fails the pumping lemma, it is definitely not regular.
True — the lemma says "regular pumps", so "does not pump not regular" by contrapositive.
If a language passes the pumping lemma, it is definitely regular.
False — that is affirming the consequent; the parent's Example 4 is exactly such a trap: it is the language , which every legal split can pump without hitting the "" bad case, yet it is still not regular.
Every finite language is regular.
True — a finite set of strings is accepted by a finite (tree-like) DFA, so the lemma never even bites (choose longer than the longest word and no qualifies).
In a non-regularity proof, you get to choose the split .
False — the lemma only guarantees some split exists; the adversary picks it, and you must defeat every legal split.
In a non-regularity proof, you get to choose the string .
True — the quantifier is in the lemma, so for the contradiction you may pick any single with .
You may choose to be a fixed string like .
False — is unknown and could exceed 10, so might fail; must depend on , e.g. .
Condition 3 only guarantees pumping up ().
False — it holds for all , including (pumping down, deleting the loop) and (the original string).
is an allowed split.
False — condition 1 forces , because the loop reads at least one symbol; a zero-length loop cannot change the string when pumped.
The pumping length must equal the number of states of the minimal DFA.
False — the proof uses for one DFA, but any also works; is "some" valid constant, not a unique one.
Every infinite regular language contains arbitrarily long strings that can be pumped.
True — any string of length has a pumpable loop, and pumping up produces unboundedly long members, so the language is infinite exactly when such a exists.
is non-regular because it "counts 's and 's".
False — there is no relation forced between and , so a simple DFA accepts ; counting only defeats regularity when counts must match.
Spot the error
"I choose and I set , then pump to break it."
Error: you cannot set . With the first symbols are all 's, so the adversary's lies inside the -block — you exploit that constraint, you do not assign .
"The lemma gives me a split with , so must be exactly the first symbol."
Error: bounds the combined length of and ; can be any non-empty chunk within the first symbols, not necessarily position 1.
" pumps because , , stays in when ."
Error: is just the original string — of course it's in . You must find one that leaves ; here gives .
"It passes for , so the language is regular."
Error: passing for a single split or a single proves nothing; you'd need it to pass for all , all splits, all — and even then it wouldn't prove regularity (only failure is conclusive).
"I proved non-regular using a string for a specific number I picked."
Error: the exponent must be tied to (like ); a fixed may be shorter than , so can fail and the lemma never applies.
"Since removed all of , the string became empty and , contradiction."
Error unless genuinely — deletes only , not and ; the result is , which is usually non-empty. Argue about 's actual form.
Why questions
Why does the proof look at only the first states of the run, not all the states?
Because pigeons in holes already forces a repeat, and staying within the first guarantees the repeat occurs early, giving for free.
Why is pigeonhole the right engine here?
A DFA has finitely many states (holes) but a long run visits more states-in-time than there are states, so some state must recur — that recurrence is the loop .
Why does choosing (rather than ) matter for ?
Because traps the loop in the front symbols; putting all 's in front forces to be pure 's, so pumping changes only the -count.
Why is often cleaner than ?
Deleting the loop shrinks a count below the required value in one step, and for palindromes it destroys front/back symmetry directly, avoiding the arithmetic of adding a repeated block.
Why can't a DFA recognise intuitively?
Its only memory is the current state, a finite bin; remembering "exactly 's seen" for unbounded needs unboundedly many states, which no finite provides.
Why does break under pumping while () does not?
The gaps between consecutive perfect squares grow past , so adding symbols lands strictly between two squares; but has no gaps, so any length is still valid.
Why must the loop read at least one symbol for the contradiction to work?
If were empty, pumping would never change the string, so would trivially stay in and you'd get no contradiction — condition 1 is what creates the change.
Why is the pumping lemma weaker than Myhill–Nerode?
Myhill–Nerode is an iff (exactly regular when finitely many equivalence classes), while pumping is only one-directional, so some non-regular languages slip past pumping but never past Myhill–Nerode.
Edge cases
Does the lemma apply to a string with ?
No — the guarantee is only for ; shorter strings need not be pumpable, so never build a proof around them.
Can be empty ()?
Yes — nothing forbids the loop from starting at the very first symbol, so may be empty; only is required non-empty.
Can be empty ()?
Yes — the repeated state can be the last one within the first , so may reach the string's end; is legal.
What if or ?
Both are regular and pass vacuously — for no exists, and for choose so no string has length ; the lemma is never triggered.
Is (all strings) pumpable?
Yes — it is regular (one accepting state loops on every symbol), and every split pumps to another accepted string, so the lemma holds trivially.
If a language is a union of a non-regular language with a large finite set, is it regular?
Not necessarily — closure under union requires both operands regular; adding a finite set to a non-regular core leaves it non-regular.
Does the same lemma work for context-free languages?
No — CFLs use a different, stronger statement (the CFL pumping lemma with two pumpable substrings ); the regular version is too weak for them.
If pumping down () keeps but pumping up () leaves , is non-regular?
Yes — condition 3 must hold for every ; a single failing breaks it, so finding leaving suffices.
Recall One-line summary of the whole game (fully quantified).
such that with , there a split with and such that . For a non-regularity proof you flip it: you fix , the adversary picks the split (obeying ), then you pick one that escapes .