Regular & Context-Free Languages: Closure and the Pumping Lemma

The pumping lemma is the standard tool for proving a language is not in a class, and it is the single most misapplied result in the subject.

The misapplication almost always comes from the quantifiers. The lemma is a nested statement with alternating "for all" and "there exists", and swapping any two of them turns a valid proof into nonsense.

The reliable way to keep them straight is to read the lemma as a game against an adversary. The adversary makes the choices bound by "there exists" in the lemma, and you make the choices bound by "for all". You win — proving the language is not regular — if you can defeat every choice the adversary is permitted to make.

The second organising fact is that the lemma is a one-way tool. It states a property every regular language has, so violating it proves non-regularity. Satisfying it proves nothing at all, because non-regular languages can satisfy it too.

That asymmetry is why Myhill-Nerode is the stronger instrument for regular languages, and why the pumping lemma survives mainly because the context-free case has no equally convenient alternative.

1. The Regular Pumping Lemma

For every regular language $L$ there exists a pumping length $p$ such that every string $w\in L$ with $|w|\ge p$ can be written as $w=xyz$ satisfying three conditions:

First, $|xy|\le p$. The pumped part occurs within the first $p$ symbols.

Second, $|y|\ge 1$. The pumped part is non-empty.

Third, $x{y}^{i}z\in L$ for every $i\ge 0$, including $i=0$, which deletes $y$ entirely.

Where the lemma comes from is worth knowing, because it makes the conditions obvious rather than arbitrary.

A DFA for $L$ has some finite number of states, say $p$. Reading a string of length at least $p$ visits at least $p+1$ states, so by the pigeonhole principle some state repeats within the first $p$ symbols.

The segment between the two visits to that state is a loop. Traversing it zero times, once, or many times all end in the same state, so all the resulting strings are accepted. That loop is $y$, and it lies within the first $p$ symbols because the repetition occurs there — which is exactly condition one.

2. The Game

Reading the lemma as a game fixes the quantifiers permanently.

You win if $x{y}^{i}z\notin L$, and you must win against every legal decomposition the adversary might choose.

The strategy follows from the structure. Choose $w$ so that the constraint $|xy|\le p$ forces $y$ into a region you can exploit. Since $y$ must lie within the first $p$ symbols, a string beginning with $p$ copies of one symbol guarantees $y$ consists only of that symbol.

Then choose $i$ to break the language's defining property, most often $i=2$ to add symbols or $i=0$ to remove them.

The commonest error is choosing $w$ after seeing the decomposition, or assuming a particular decomposition. The adversary chooses it, so the argument must handle all of them at once.

3. Using It Correctly

Consider $L=\{a^n{b}^n:n\ge 0\}$.

The adversary gives $p$. Choose $w=a^p{b}^p$, which is in $L$ and has length $2p\ge p$.

The adversary must decompose $w=xyz$ with $|xy|\le p$. Since the first $p$ symbols of $w$ are all $a$s, both $x$ and $y$ consist entirely of $a$s, and $|y|\ge 1$ means $y$ has at least one $a$.

Choose $i=2$. Then $x{y}^{2}z$ has more $a$s than the original but exactly the same number of $b$s, so the counts no longer match and the string is not in $L$.

Every legal decomposition is defeated, because the constraint $|xy|\le p$ left the adversary no choice about which symbols $y$ could contain.

Notice what the choice of $w$ accomplished. Had we chosen $w=(ab{)}^p$, the adversary could pick $y=ab$, and pumping would give $(ab{)}^{p+1}$ — which is not in $L$ either, but the reasoning becomes fiddlier. A well-chosen $w$ removes the adversary's freedom.

4. The Context-Free Pumping Lemma

For every context-free language $L$ there exists a pumping length $p$ such that every $w\in L$ with $|w|\ge p$ can be written as $w=uvxyz$ satisfying:

First, $|vxy|\le p$. The pumped region is confined to a window of length $p$.

Second, $|vy|\ge 1$. At least one of the two pumped pieces is non-empty.

Third, $u{v}^{i}x{y}^{i}z\in L$ for every $i\ge 0$. Both pieces are pumped the same number of times.

Two pieces are pumped rather than one, and the reason comes from the proof, which uses a parse tree rather than a state sequence.

In a grammar in Chomsky normal form, a long enough string forces a path in the parse tree that repeats some variable $A$. The subtree rooted at the upper $A$ derives $vxy$, and the subtree at the lower $A$ derives $x$.

Replacing the lower subtree with a copy of the upper one duplicates both $v$ and $y$ together, because they sit on opposite sides of the inner subtree. That structural fact is why the two pieces must be pumped in lockstep.

The window constraint $|vxy|\le p$ is the analogue of $|xy|\le p$, arising from bounding how far apart the two occurrences of $A$ can be.

5. Applying the Context-Free Version

The context-free lemma is harder to use because the adversary has more freedom: five pieces instead of three, and the pumped region can sit anywhere within a window rather than at the start.

Consider $L=\{a^n{b}^n{c}^n:n\ge 0\}$.

Choose $w=a^p{b}^p{c}^p$.

The adversary picks $uvxyz$ with $|vxy|\le p$. Because the window has length at most $p$ and each symbol block has length exactly $p$, the window cannot span all three blocks. It touches at most two adjacent blocks.

Choose $i=2$. Pumping increases the counts of the symbols inside the window and leaves the third block untouched.

Whichever two blocks the window covers, the third is left behind, so the three counts can no longer be equal and the string leaves $L$.

The case analysis is what makes context-free proofs longer, but it is usually short: enumerate which blocks the window can touch and show each case fails.

6. What the Lemma Cannot Do

The lemma states a necessary condition, not a sufficient one.

Every regular language satisfies it, so a language violating it is not regular. But a non-regular language can satisfy it, so satisfying it proves nothing.

There exist non-regular languages that pump perfectly, and one is $\{a^i{b}^j{c}^k:i=0\text{ or }j=k\}$. Any string with no $a$s can be pumped in the $a$ region trivially, and any string with at least one $a$ can be pumped on that $a$ to stay in the language via the first clause.

The language is not regular, but the pumping lemma cannot show it. Myhill-Nerode can, which is why it is the stronger tool.

The practical consequence for exams is precise. A question asking you to prove a language is not regular expects the pumping lemma or Myhill-Nerode. A question asking whether a language is regular cannot be answered by pumping, and an option claiming "it satisfies the pumping lemma, therefore it is regular" is always wrong.

7. The Chomsky Hierarchy

The four language classes nest strictly, each with its own grammar restriction and machine model.

Each containment is strict. The language $a^n{b}^n$ separates types 3 and 2. The language $a^n{b}^n{c}^n$ separates types 2 and 1. The halting problem's language separates decidable from recursively enumerable.

Context-sensitive grammars are non-contracting: the right-hand side is never shorter than the left. That single restriction is what bounds the tape and gives the linear bounded automaton.

The closure properties across the hierarchy are examined as a table.

The two gaps are the examinable content. Context-free languages fail intersection and complement; recursively enumerable languages fail complement.

Recursively enumerable languages fail complement for a specific reason. A language and its complement being both recursively enumerable would make the language decidable, by running both semi-deciders in parallel until one halts. Since undecidable recursively enumerable languages exist, the class cannot be closed under complement.

8. Worked Examples

Example 1. Prove that $L=\{ww:w\in \{a,b{\}}^{\ast }\}$ is not regular.

The adversary gives $p$.

Choose $w^{\prime }=a^{p}b{a}^{p}b$, which is in $L$ with $w=a^{p}b$, and has length $2p+2\ge p$.

The adversary decomposes $w^{\prime }=xyz$ with $|xy|\le p$ and $|y|\ge 1$. Since the first $p$ symbols are all $a$s, $y$ consists of $k$ copies of $a$ for some $k\ge 1$.

Choose $i=0$, deleting $y$.

The result is $a^{p-k}b{a}^{p}b$.

For this to be in $L$ it would have to split into two equal halves. Its length is $2p+2-k$.

If $k$ is odd the length is odd, so no split into two equal halves exists at all.

If $k$ is even, the first half ends in an $a$ while the second half ends in a $b$, since the only two $b$s sit at position $p+1-k$ and at the very end. The halves therefore differ.

Either way the string is not in $L$, so the language is not regular.

Note the choice of $w^{\prime }$. A simpler candidate like $a^p{a}^p$ fails, because deleting $a$s from it can still leave a string of the form $ww$. Including the $b$s pins the structure down.

Example 2. Prove that $L=\{a^{n^2}:n\ge 0\}$ is not regular.

The adversary gives $p$.

Choose $w=a^{p^2}$, whose length is $p^2\ge p$.

The adversary picks $y=a^k$ with $1\le k\le p$, since $|xy|\le p$ confines it.

Choose $i=2$. The pumped string is $a^{p^2+k}$.

For this to be in $L$, the exponent must be a perfect square. The next square after $p^2$ is $(p+1{)}^2=p^2+2p+1$.

Since $k\le p$, we have $p^2<p^2+k\le p^2+p<p^2+2p+1$.

The pumped length falls strictly between two consecutive squares, so it is not a square and the string is not in $L$.

The language is therefore not regular. The argument works because squares grow further apart as they grow larger, while the pumping lemma can only add a bounded amount.

Example 3. Prove that $L=\{a^n{b}^n{c}^n:n\ge 0\}$ is not context-free.

The adversary gives $p$.

Choose $w=a^p{b}^p{c}^p$, whose length is $3p\ge p$.

The adversary decomposes $w=uvxyz$ with $|vxy|\le p$ and $|vy|\ge 1$.

The window $vxy$ has length at most $p$, and each symbol block has length exactly $p$, so the window cannot reach from the $a$ block into the $c$ block. It touches at most two adjacent blocks.

Three cases arise.

Case 1: the window lies within one block. Pumping with $i=2$ increases that symbol's count and leaves the other two unchanged, so the counts differ.

Case 2: the window spans the $a$ and $b$ blocks. Pumping increases the $a$ count, the $b$ count, or both, but the $c$ count is untouched, so equality fails.

Case 3: the window spans the $b$ and $c$ blocks. By the same argument the $a$ count is untouched.

In every case $u{v}^{2}x{y}^{2}z\notin L$, so the language is not context-free.

Note that this language is context-sensitive, sitting one level up in the hierarchy, which is exactly what makes it the standard separator between types 2 and 1.

Example 4. Explain why the language $\{a^i{b}^j{c}^k:i=0\text{ or }j=k\}$ satisfies the pumping lemma despite not being regular.

Take the pumping length $p=1$ and consider any string $w\in L$ with $|w|\ge 1$.

Case A: $w$ begins with an $a$. Then $i\ge 1$, so the language membership must come from the second clause, meaning $j=k$. Decompose with $x=ϵ$, $y=a$, and $z$ the rest.

Pumping gives $a^{i^{\prime }}{b}^j{c}^k$ for various $i^{\prime }$. Every such string still has $j=k$, so it remains in $L$ regardless of how many $a$s there are.

Case B: $w$ begins with a $b$ or a $c$. Then $i=0$, and the first clause holds. Decompose with $y$ as the first symbol.

Pumping changes the $b$ or $c$ count, but $i$ remains 0, so the first clause still holds and the string stays in $L$.

Every string pumps successfully, so the language satisfies the lemma.

Yet the language is not regular. Myhill-Nerode shows this: the strings $ab,abb,abbb,\dots$ are pairwise distinguishable, since appending $c^j$ accepts exactly the one with $j$ matching $b$s.

This is the concrete demonstration that the pumping lemma is necessary but not sufficient, and why an exam option asserting regularity from pumping success is always wrong.

Example 5. Prove that the recursively enumerable languages are not closed under complement.

Suppose, for contradiction, that they were.

Take any recursively enumerable language $L$. By assumption its complement is also recursively enumerable, so there are Turing machines $M_1$ semi-deciding $L$ and $M_2$ semi-deciding its complement.

Semi-deciding means halting and accepting on members, and possibly running forever on non-members.

Now build a machine that runs $M_1$ and $M_2$ in parallel on the input, interleaving their steps.

Every string is in exactly one of $L$ or its complement, so exactly one of the two machines will eventually halt and accept.

When $M_1$ halts, output "yes". When $M_2$ halts, output "no". The combined machine always halts, so it decides $L$.

That would make every recursively enumerable language decidable.

But undecidable recursively enumerable languages exist — the halting problem's language is the standard example, being semi-decidable by simulation and undecidable by diagonalisation.

The contradiction shows the assumption is false, so the class is not closed under complement.

The same argument gives the useful positive result: if a language and its complement are both recursively enumerable, the language is decidable. That equivalence is examined directly.

Example 6. Where does each of these sit in the Chomsky hierarchy: $\{a^n{b}^n\}$, $\{a^n{b}^n{c}^n\}$, $\{ww\}$, and the set of strings encoding halting Turing machines?

$\{a^n{b}^n\}$ is context-free but not regular. A grammar with $S\to aSb\mid ϵ$ generates it, and the pumping lemma or Myhill-Nerode rules out regularity.

$\{a^n{b}^n{c}^n\}$ is context-sensitive but not context-free. The context-free pumping lemma rules out type 2, as shown above. A linear bounded automaton can verify the three counts by making multiple passes over the tape, so it is type 1.

$\{ww\}$ is context-sensitive but not context-free. This is more surprising than it looks, since $\{w{w}^R\}$ — the palindromes — is context-free. The reversal is what a stack can check; matching a copy in the same order is not, because the stack would deliver the first half backwards.

The halting language is recursively enumerable but not recursive. A universal machine can simulate the encoded machine and halt if it does, which semi-decides it. Diagonalisation shows no machine can decide it, so it sits strictly inside type 0 and outside the recursive languages.

The pattern worth extracting is that each level is separated by a specific structural demand: one nesting for type 2, more than one comparison for type 1, and unbounded search for type 0.

Summary

The pumping lemma is a game: the adversary chooses the pumping length and the decomposition, you choose the string and the pumping count, and you win by defeating every legal decomposition.

For regular languages, $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{i}z\in L$ for all $i\ge 0$. It comes from a repeated state in a DFA, which is why the loop lies within the first $p$ symbols.

Choose $w$ so that the window constraint forces $y$ into a single symbol block, then pump to break the counting property.

For context-free languages, $w=uvxyz$ with $|vxy|\le p$, $|vy|\ge 1$, and both $v$ and $y$ pumped together. Two pieces appear because a repeated variable in a parse tree duplicates the material on both sides of the inner subtree.

The window cannot span three blocks of length $p$ each, which is what makes the three-symbol language provably non-context-free by case analysis.

The lemma is necessary and not sufficient. Non-regular languages exist that pump perfectly, so satisfying the lemma proves nothing, and Myhill-Nerode is the stronger tool for regular languages.

The Chomsky hierarchy nests strictly: regular, context-free, context-sensitive, recursively enumerable, with separating languages at each boundary and a machine model for each level.

Context-free languages fail intersection and complement; recursively enumerable languages fail complement, because a language and its complement both being semi-decidable would make it decidable.