Example- Pumping Lemma For CFL

 

Using the Pumping Lemma to Show a Language is Not Context-Free

We will use the pumping lemma for context-free languages to prove that:

$$L = \{ a^n b^n c^n \mid n \ge 1 \}$$

is not a context-free language.

---

Proof

Step 1: Assume $L$ is context-free

Suppose, for contradiction, that $L$ is a context-free language.

Then, by the pumping lemma, there exists a positive integer $m$ such that
any string $\omega \in L$ with $|\omega| \ge m$ can be written as:

$$\omega = u v x y z$$

satisfying:

1. $|v x y| \le m$
   

2. $|v y| \ge 1$
   

3. $u v^i x y^i z \in L$ for all $i=0,1,2,\dots$

---

Step 2: Choose a specific string in $L$

Let us take:

$$\omega = a^m b^m c^m$$

Clearly, $\omega \in L$ and $|\omega| = 3m \ge m$.

---

Step 3: Analyze the possible locations of $v$ and $y$

Because $|v x y| \le m$
the substring $v x y$ must lie within a span of length $m$ in $\omega$.
That means $v x y$ can only cover a limited portion of $\omega$ —
it cannot stretch over all three regions (the block of a’s, b’s, and c’s).

Hence, $v$ and $y$ can appear in one of the following ways:

(a) Entirely within the block of a’s

(b) Entirely within the block of b’s

(c) Entirely within the block of c’s

(d) Across the boundary between a’s and b’s

(e) Across the boundary between b’s and c’s

We will show in each case that $u v^i x y^i z \notin L$ for some $i$.

---

Step 4: Consider all possible cases

Case (a): $v y$ lies entirely within the a’s

Then $v$ and $y$ contain only a’s.

When we pump $i = 2$, the number of a’s increases,
but the number of b’s and c’s remains the same.

Resulting string:

$$u v^2 x y^2 z = a^{m + k} b^m c^m \quad (k > 0)$$

This string is not in $L$ because the numbers of a’s, b’s, and c’s are no longer equal.

---

Case (b): $v y$ lies entirely within the b’s

Then $v$ and $y$ contain only b’s.

Pumping increases or decreases the number of b’s without changing a’s or c’s:

$$u v^2 x y^2 z = a^m b^{m+k} c^m$$

This is not in $L$ since the counts differ.

---

Case (c): $v y$ lies entirely within the c’s

Similar to case (a):

$$u v^2 x y^2 z = a^m b^m c^{m+k}$$

This is not in $L$.

---

Case (d): $v y$ spans the boundary between a’s and b’s

Then $v$ contains some a’s and $y$ contains some b’s.

When we pump $i = 2$, we add extra a’s and b’s simultaneously,but not the same number necessarily, and no extra c’s.

Resulting string:

$$u v^2 x y^2 z$$

contains unequal numbers of a’s, b’s, and c’s → not in $L$.

---

Case (e): $v y$ spans the boundary between b’s and c’s

Similarly, pumping changes the number of b’s and c’s differently, producing a string with unequal counts.

Thus again $u v^2 x y^2 z \notin L$

---

Step 5: Conclusion

In all possible cases, pumping changes the balance among a’s, b’s, and c’s.Therefore, there exists some $i$ (such as $i=\mathrm{0\; or }$$i = 2$) for which:

$$u v^i x y^i z \notin L$$

This contradicts the third condition of the pumping lemma.

Hence, our assumption that $L$ is context-free must be false.

$$\boxed{L = \{ a^n b^n c^n \mid n \ge 1 \} \text{ is not a context-free language.}}$$

---

🧠 Intuitive Summary 

• Pumping lemma tells us every long enough CFL string can be “pumped” by repeating some substrings $v$ and $y$.

• For $a^n b^n c^n$, the balance of a’s, b’s, and c’s is strict.

• Pumping always destroys that balance.

• Therefore, no context-free grammar (and hence no PDA) can generate this language.