Pumping Lemma for Context Free Languages (CFLs) | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Part V. Pumping Lemma for Context Free Languages (CFLs)
Consider the following figure:

From the diagram, we can say that not all languages are context free languages. All context free languages are context sensitive and unrestricted. But all context sensitive and unrestricted languages are not context free from the above diagram.
We have a mechanism to show that some languages are not context free. The pumping lemma for CFLs allow us to show that some languages are not context free.

12 Pumping lemma for CFLs
Let G be a CFG. Then there exists a constant, n such that if W is in L(G) and |W| ≥ n, then we may write W = uvxyz such that,
1. |vy| ≥ 1 that is either v or y is non-empty,
2. |vxy| ≤ n then for all i ≥ 0,
uvⁱxyⁱz is in L(G).
This is known as pumping lemma for context free languages.

Pumping lemma for CFLs can be used to prove that a language, L is not context free.
We assume L is context free. Then we apply pumping lemma to get a contradiction.
Following are the steps:
Step 1:
Assume L is context free. Let n be the natural number obtained by using the pumping lemma.
Step 2:
Choose W ∈ L so that |W| ≥ n. Write W = uvxyz using the pumping lemma.
Step 3:
Find a suitable k so that uv^kxy^kz /∈ L. This is a contradiction, and so L is not context free.

Examples:
Example 1:
Show that L = {aⁿbⁿcⁿ|n ≥ 1} is not context free.

Step 1:
Assume L is context free. Let n be the natural number obtained by using the pumping lemma.
Step 2:
Choose W ∈ L so that |W| ≥ n. Write W = uvxyz using the pumping lemma.
Let W = aⁿbⁿcⁿ. Then |W| = 3n > n.

Write W = uvxyz, where |vy| ≥ 1, that is, at least one of v or x is not ε.
Step 3:
Find a suitable k so that uv^kxy^kz /∈ L. This is a contradiction, and so L is not context free.
uvxyz = aⁿbⁿcⁿ. As 1 ≤ |vy| ≤ n, v or x cannot contain all the three symbols a, b, c.

i) So v or y is of the form aⁱb^j(or b^jc^j) for some i,j such that i + j ≤ n. or
ii) v or y is a string formed by the repetition of only one symbol among a, b, c.
When v or y is of the form aⁱb^j, v2 = aⁱb^jaⁱb^j(or y² = aⁱb^jaⁱb^j). As v² is a substring of the form uv²xy²z,we cannot have uv²xy²z of the form a^mb^mc^m. So uv²xy²z ∉ L.

When both v and y are formed by the repetition of a single symbol (example: u = aⁱ and v = b^j for some iand j, i ≤ n, j ≤ n), the string uxz will contain the remaining symbol, say a₁.Also  will be a substring of uxz as a₁ doesnot occur in v or y. The number of occurrences of one of the other two symbols in uxz is less than n (recall uvxyz = aⁿbⁿcⁿ),and n is the number of occurrences of a₁. So uv⁰xy⁰z = uxz ∉ L. Thus for any choice of v or y , we get a contradiction. Therefore, L is not context free.

Example 2:
Show that L = {a^p|p is a prime number} is not a context free language.

This means, if w ∈ L, number of characters in w is a prime number.
Step 1:
Assume L is context free. Let n be the natural number obtained by using the pumping lemma.
Step 2:
Choose W ∈ L so that |W| ≥ n. Write W = uvxyz using the pumping lemma.
Let p be a prime number greater than n. Then w = a^p ∈ L.

We write W = uvxyz
Step 3:
Find a suitable k so that uv^kxy^kz /∈ L. This is a contradiction, and so L is not context free.
By pumping lemma, uv⁰xy⁰z = uxz ∈ L.
So |uxz| is a prime number, say q.
Let |vy| = r.
Then |uv^qxy^qz| = q + qr.
Since, q + qr is not prime, uv^qxy^qz ∉ L. This is a contradiction. Therefore, L is not context free.

Example 3:
Show that the language L = {aⁿbⁿcⁿ|n ≥ 0} is not context free.

Step 1:
Assume L is context free. Let n be the natural number obtained by using the pumping lemma.
Step 2:
Choose W ∈ L so that |W| ≥ n. Write W = uvxyz using the pumping lemma.
Let W = aⁿbⁿcⁿ.

We write W = uvxyz where |vy| ≥ 1 and |vxy| ≤ n, then
pumping lemma says that uvⁱxyⁱz ∈ L for all i ≥ 0.

Observations:
a. But this is not possible; because if v or y contains two symbols from {a,b,c} then uv²xy²z contains a ’b’ before an ’a’or a ’c’ before ’b’, then uv²xy²z will not be in L.
b. In other case, if v and y each contains only a’s, b’s or only c’s, then uvⁱxyⁱ cannot contain equal number of a’s, b’s and c’s. So uvixyiz will not be in L.
c. If both v and y contains all three symbols a, b and c, then uv²xy²z will not be in L by the same logic as in observation (a).
So it is a contradiction to our statement. So L is not context free.

Step 3:
Find a suitable k so that uv^kxy^kz ∉ L. This is a contradiction, and so L is not context free.

By pumping lemma, uv⁰xy⁰z = uxz ∈ L.
So |uxz| is a prime number, say q.
Let |vy| = r.
Then |uv^qxy^qz| = q + qr.
Since, q + qr is not prime, uv^qxy^qz ∉ L. This is a contradiction. Therefore, L is not context free.