Pumping Lemma for Context Free Languages (CFLs) - Theory of Computation

Part V. Pumping Lemma for Context Free Languages (CFLs)

Consider the following figure:

From the diagram, we can conclude that not all languages are context free. Every context-free language (CFL) is also a context-sensitive and an unrestricted (recursively enumerable) language, but the converses do not hold: there exist context-sensitive and unrestricted languages that are not context free. The pumping lemma for CFLs gives a mechanical way to prove that certain languages are not context free.

12 Pumping lemma for CFLs

Let G be a context-free grammar (CFG). Then there exists a constant n (depending on G) such that if a string W belongs to L(G) and its length satisfies |W| ≥ n, then W can be written as

\[ W = u v x y z \]

1. \[ |v y| \ge 1 \] - that is, at least one of v or y is non-empty.
2. \[ |v x y| \le n \]
3. For all integers \(i \ge 0\), the pumped string

\[ u v^{\,i} x y^{\,i} z \in L(G). \]

This statement is the pumping lemma for context-free languages. Informally, it says that any sufficiently long string generated by a CFG contains a region that can be "pumped" (duplicated or removed) in two places while remaining in the language.

Sketch of the proof idea

One standard proof uses grammars in Chomsky Normal Form (CNF). In CNF every internal node of a parse tree has exactly two children. If the parse tree for a string is tall enough (height greater than the number of variables in the grammar), then along some path from the root to a leaf a variable must repeat. The repeated variable yields two subtrees whose yields allow the decomposition \(W = u v x y z\) and the pumping property. The bound n can be chosen from the number of variables (nonterminals) of the grammar.

How to use the pumping lemma to show a language is not context free

1. Assume the language \(L\) is context free. Let \(n\) be the pumping length given by the lemma.
2. Choose a specific string \(W \in L\) with \(|W| \ge n\). Decompose \(W = u v x y z\) as guaranteed by the lemma (so \(|v y| \ge 1\) and \(|v x y| \le n\)).
3. Find an integer \(i\) (often \(i=0\) or \(i=2\), or some function of lengths appearing) such that the pumped string \(u v^{\,i} x y^{\,i} z\) is not in \(L\). This contradiction shows \(L\) is not a CFL.

Examples

Example 1

Show that \(L = \{\, a^{n} b^{n} c^{n} \mid n \ge 1 \,\}\) is not context free.

Step 1:

Assume \(L\) is context free. Let \(n\) be the pumping length provided by the lemma.

Step 2:

Choose

\[ W = a^{n} b^{n} c^{n}, \]

so \(|W| = 3n \ge n\). By the pumping lemma write

\[ W = u v x y z \]

with \(|v y| \ge 1\) and \(|v x y| \le n\).

Step 3 (case analysis):

Because \(|v x y| \le n\), the substring \(v x y\) lies entirely within a block of at most two consecutive symbol types among the three blocks \(a^{n}, b^{n}, c^{n}\). Therefore the possibilities are:

• Both \(v\) and \(y\) occur within the same block of identical symbols (all a's, or all b's, or all c's).
• One of \(v\) or \(y\) lies in the last part of one block and the other lies in the beginning of the next block, so they cover two symbol types (for example, some a's and some b's, or some b's and some c's).

In every case, pumping changes the relative numbers or the order of symbols so the pumped string cannot remain of the form \(a^{m} b^{m} c^{m}\) for any \(m\). Concretely:

• If \(v\) and \(y\) are within one block, pumping (take \(i=0\) or \(i=2\)) changes the count of that symbol only, so counts of a, b, c are no longer all equal.
• If \(v\) and/or \(y\) span two blocks (say some a's and some b's), pumping will either introduce a b before all a's are finished or will change counts inconsistently; again the form \(a^{m} b^{m} c^{m}\) is destroyed.

Thus for any allowed decomposition guaranteed by the pumping lemma, there exists \(i\) with \(u v^{\,i} x y^{\,i} z
otin L\). This contradiction proves \(L\) is not context free.

Example 2

Show that \(L = \{\, a^{p} \mid p \text{ is a prime number} \,\}\) is not context free.

Step 1:

Assume \(L\) is context free and let \(n\) be the pumping length.

Step 2:

Choose a prime \(p > n\) and consider

\[ W = a^{p} \in L. \]

Write \(W = u v x y z\) with \(|v y| \ge 1\) and \(|v x y| \le n\).

Step 3:

By the pumping lemma \(u x z = u v^{\,0} x y^{\,0} z \in L\). Let

\[ |u x z| = q, \]

so \(q\) is a prime (since \(u x z \in L\)). Let

\[ |v y| = r \ge 1. \]

Now consider the string pumped with \(i = q\):

\[ |u v^{\,q} x y^{\,q} z| = q + q r = q(1+r). \]

Because \(r \ge 1\), the product \(q(1+r)\) is composite, so \(u v^{\,q} x y^{\,q} z
otin L\). This contradicts the pumping lemma requirement that all pumped strings lie in \(L\). Hence \(L\) is not context free.

Example 3

Show that \(L = \{\, a^{n} b^{n} c^{n} \mid n \ge 0 \,\}\) is not context free.

The language in Example 1 started at \(n\ge 1\); allowing \(n=0\) only adds the empty string to the language and does not affect the pumping argument. The same proof as Example 1 applies: pick \(W = a^{n} b^{n} c^{n}\) with \(n\) at least the pumping length, apply the lemma, and analyse cases for where \(v\) and \(y\) lie. In every possible decomposition pumping produces a string not of the form \(a^{m} b^{m} c^{m}\). Therefore this language is also not context free.

Remarks and common pitfalls

• The pumping lemma is a necessary condition for a language to be context free but not a sufficient condition: satisfying the pumping property does not guarantee a language is context free.
• When applying the lemma to prove a language is not CFL, you should choose the witness string W carefully (usually depending on the pumping length \(n\)) so that every possible decomposition \(u v x y z\) leads to a contradiction.
• Carefully separate cases for where \(v\) and \(y\) can lie. Use \(i=0\) (delete), \(i=2\) (duplicate), or other values of \(i\) as required to force a violation of the language definition.
• A common mistake is assuming the pumping region \(v x y\) can cover the whole string; in fact \(|v x y| \le n\) restricts it to a bounded region.

Summary

The pumping lemma for CFLs is a standard tool to prove that particular languages are not context free. Its formal statement gives a decomposition and a pumping property for sufficiently long strings of any CFL. The usual method of proof by contradiction-choosing a long string and showing every valid decomposition yields a pumped string outside the language-works for many important non-CFLs such as \(\{a^{n}b^{n}c^{n}\}\) and the set of prime-length unary strings.