Pumping lemma for CFLs

Why it exists

Regular languages are limited because a finite state repeats; context-free languages are limited because a variable repeats in a long parse tree, and the part of the string derived between two occurrences of that variable can be repeated on both sides. The pumping lemma for CFLs turns this into a test: if a language has no such repeatable pair of parts, it is not context-free. GATE asks it for the standard languages ($a^n b^n c^n$, $ww$, ...) and as true/false statements.

Prerequisites

You need closure properties of CFLs (closure properties) and Chomsky normal form (normal forms); the structure of the argument is that of the regular pumping lemma.

Precise definitions

Pumping lemma for context-free languages. If $L$ is context-free, there is an integer $p \ge 1$ such that every string $s \in L$ with $|s| \ge p$ can be written $s = u\,v\,x\,y\,z$ with

1. $|v\,y| \ge 1$ (at least one of $v, y$ is not empty),
2. $|v\,x\,y| \le p$,
3. $u\,v^i\,x\,y^i\,z \in L$ for every $i \ge 0$.

The two pumped parts $v$ and $y$ are pumped together, the same number of times. As for regular languages the lemma is only a necessary condition: it can prove that a language is not context-free, never that it is.

Proof sketch (textbook). Take a grammar in Chomsky normal form with $m$ variables and $p = 2^m$. A parse tree is binary, so a string of length at least $2^m$ has a root-to-leaf path with more than $m$ variables on it, and some variable $A$ occurs twice on it; take the repetition nearest the leaf. The lower $A$ derives $x$, the upper $A$ derives $v\,x\,y$ (the string between has two sides, because the tree is binary and the upper $A$ has another child on one side). The tree can be cut at the lower $A$ and replaced by the upper subtree, or the upper subtree repeated: $A \Rightarrow^* v A y$, so $u v^i x y^i z$ is derivable. Choosing the lowest repetition keeps $|vxy| \le 2^m$; one side of the split is nonempty, which gives $|vy| \ge 1$. The value $p = 2^m$ was checked empirically (below).

How it works

The game

To show $L$ is not context-free:

1. The adversary picks $p$.
2. You pick a string $s \in L$ with $|s| \ge p$.
3. The adversary picks any decomposition $s = uvxyz$ with $|vxy| \le p$ and $|vy| \ge 1$.
4. You pick $i \ge 0$ with $u v^i x y^i z \notin L$.

If you win for every $p$ and every decomposition, $L$ is not context-free. The table plays it with $p = 4$ for six non-context-free languages and for the context-free language $a^n b^n$, listing the number of legal decompositions and how many survive $i = 0, \ldots, 9$:

Every decomposition of the six strings fails; for $a^n b^n$ (which is context-free) seven survive, for example $v = a$, $y = b$ pumped together. The reasoning behind the failures:

$\{a^n b^n c^n\}$. Take $s = a^p b^p c^p$. Since $|vxy| \le p$, the window $vxy$ cannot touch all three letters: it misses $a$'s or $c$'s completely. If $v, y$ contain only symbols from at most two of the three blocks, pumping up (or down) changes the number of those letters but not the third, so the counts are no longer equal.

$\{ww\}$. Take $s = a^p b^p a^p b^p = tt$ with $t = a^p b^p$. A case analysis on where the window $vxy$ (length $\le p$) lies, in the first half, in the second half or straddling the middle, shows that pumping with $i = 0$ or $i = 2$ always produces a string that is not of the form $t't'$: in the first two cases the midpoint of the pumped string moves into a block of the other symbol, in the third the two blocks next to the middle become unequal in size. The program tries every decomposition (415 of them for $p = 4$) and none survives.

$\{a^i b^j c^k : i < j < k\}$. Take $s = a^p b^{p+1} c^{p+2}$. The window cannot contain both an $a$ and a $c$ (there are $p + 1$ $b$'s between them). If $vy$ has no $c$: pump up with $i = 2$, so the $c$'s stay at $p + 2$. If $vy$ contains an $a$, the $a$'s reach at least $p + 1$; the order $i < j$ could then survive only if $b$'s were added too, but then $j \ge p + 2 = k$ and $j < k$ fails (and if no $b$ was added, $j = p + 1 \le i$ fails). If $vy$ has only $b$'s, then $j \ge p + 2 = k$ and $j < k$ fails. If $vy$ contains a $c$ (and no $a$): pump down with $i = 0$; if a $b$ is removed then $j \le p$ while $i = p$, and if only $c$'s are removed then $k \le p + 1 = j$: again the order fails.

$\{a^{n^2}\}$. Take $s = a^{p^2}$. Pumping once gives length $p^2 + k$ with $1 \le k \le |vy| \le p$, strictly between consecutive squares $p^2$ and $(p + 1)^2$.

$\{a^q : q \text{ prime}\}$. Take a prime $q \ge p$ and pump with $i = q + 1$: the length is $q + q\,|vy| = q(1 + |vy|)$, composite. (A unary context-free language is regular, a textbook fact, so every unary non-regular language such as this one is automatically not context-free.)

$\{a^i b^j c^k d^l : i = k \text{ and } j = l\}$. Take $a^p b^p c^p d^p$. The window touches at most two neighbouring blocks, so pumping breaks one of the two crossing equalities.

Why $|vxy| \le p$ matters

Without the bound the adversary could choose $v$ and $y$ far apart. Take $\{a^i b^j c^k d^l : i = k \text{ and } j = l\}$ and $s = a^p b^p c^p d^p$: with $v = a$, $x = b^p$, $y = c$ (a window of length $p + 2$) pumping $v$ and $y$ together keeps $i = k$ and does not touch $j$ and $l$, so this decomposition survives. The bound $|vxy| \le p$ forbids it, and with the bound every decomposition fails.

Choosing the string

Make the language's equalities cross each other and put the blocks so that a window of length $p$ can touch only part of the structure (blocks of length $p$ separated by blocks of length $p$). For $a^i b^j c^k$ with an inequality use the string just on the boundary and pump up or down as needed.

Worked examples

Cheat box

Traps and GATE patterns

Connections

It is the context-free counterpart of the regular pumping lemma (regular languages); it gives the witness $a^n b^n c^n$ for the closure counterexamples (closure of CFLs) and for the next level of the Chomsky hierarchy (hierarchy).

PYQs

Let Σ = {a, b, c, d} and let L = { aibjckdl | i, j, k, l ≥ 0
}.
Which of the following constraints ensure(s) that the
language L is context-free?

Consider the following two languages over the alphabet
{a, b, c}, where m and n are natural numbers.
L1 = {ambmcm+n | m, n ≥ 1}
L2 = {ambncm+n | m, n ≥ 1}
Which ONE of the following statements is CORRECT?

THEORY OF COMPUTATION

Consider the following languages:
L1 = {ww | w ∈ {a, b}* }
L2 = {anbncm | m, n≥ 0}
L3 = {ambncn | m, n≥ 0}
Which of the following statements is/are FALSE?

For a string w, we define wR to be the reverse of w. For
example, if w= 01101 then wR= 10110. Which of the
following languages is/are context-free?

Consider the following languages.
L1 = {wxyx | w, x, y ε (0 + 1)+}
L2 = {xy | x, y ε(a + b)*, |x| = |y|, x !=y}
Which one of the following is TRUE?

Which one of the following languages over Σ = {a,b}  is
NOT context-free?

Consider the following languages:
I.{ambncpdq |m + p = n + q,where m,n,p,q >= 0}
II.{ambncpdq |m=n and p=q,where m,n,p,q >= 0}
III.{ambncpdq |m=n and p!=q,where m,n,p,q>= 0}
IV.{ambncpdq |mn = p + q, where m, n, p, q>= 0}
Which of the above languages are context-free?

Consider the following languages:
L1 = {ap│p is a prime number}
L2 = {anbmc2m | n ≥ 0, m ≥ 0}
L3 = {anbnc2n │ n ≥ 0}
L4 = {anbn │ n ≥ 1}
Which of the following are CORRECT?
I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive.
IV. L4 is deterministic context-free.

Consider the following languages:
L1 = {anbmcn+m: m, n > 1}
L2 = {anbnc2n: n > 1}
Which one of the following is TRUE?

Consider the languages
L1 = {0 i1 j | i != j}.
L2 = {0 i1 j | i = j}.
L3 = {0 i1 j | i = 2j+1}.
L4 = {0 i1 j | i!= 2j}.
Which one of the following statements is true?

Let
L1 = {0n+m1n0m | n, m >= 0},
L2 = {0n+m1n+m0m | n, m >= 0} and
L3 = {0n+m1n+m0n+m | n, m >= 0}.
Which of these languages are NOT context free?

Self-check

Revision card

References