Pumping lemma for CFL
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@iitj.ac.in
Formerly at department of Computer Science and Engineering
MBM Engineering College, Jodhpur

Saturday 19th July, 2025

kr chowdhary

TOC

1/ 8

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Pumping Lemma for CFLs
Given any CFG G, L = (G ), we can convert it to CNF. The
parse-tree creates a Binary-tree.
Let G has V1 . . . Vm variables. Choose this as the value of longest
path in the derivation-tree (= 2m )(for G to be in CNF). A constant
p can be chosen such that p = 2m .
Let w = uvxyz, |w | ≥ p and w ∈ L(G ). Then followings hold:
1. A string in L of length m or less has yield length of 2m−1 or less.
2. Since p = 2m , ∴ 2m−1 = p/2
3. ∴, w is too long to be yielded (obtained) from a parse-tree of
length (i.e. height) m.
Pumping Lemma for CFLs: (Bar-Hillel Lemma):
If a language L is CF, then there exists some integer p ≥ 1 such that
any string in L with |w | ≥ p (where p is pumping length) can be
written as: w = uvxyz, with substrings u, v , x, y , z, such that
|uxy | ≥ p, |vy | ≥ 1 and,
uv n xy n x ∈ L for every integer n ≥ 0.
All CF languages are guaranteed to satisfy this property.
kr chowdhary

TOC

2/ 8

Pumping Lemma for CFLs
For a parse-tree of length m + 1, choose a path to be m + 1, yield
must be 2m , and |w | ≤ p.
Any parse-tree that yields w must have a path of at least m + 1.
w = uvxyz, |w | ≥ p.

if k ≥ m then at least 2 of these variables must be same (since there
are m unique variables).
Suppose the variables are same at Ai = Aj , where 1 ≤ i < j ≤ k.

kr chowdhary

TOC

3/ 8

Pumping Lemma for CFLs . . .

Case of vy ̸= ε: The v , y cannot be terminals, otherwise there
would not be Aj .
∴ we must have two variables, one of them must lead to Aj and
other must lead to v or y or both.
Case of |vxy | ≤ p: (The middle portion is no longer than p). That
is yield of subtree rooted at Ai , or for the longest path of m + 1,
|vxy | ≤ p ≤ 2m+1−1 . In case of Ai as A0 , vxy is entire tree.

kr chowdhary

TOC

4/ 8

Pumping Lemma for CFLs . . .
Case of ∀i ≥ 0, uv i xy i z ∈ L :
We can show this by Ai = Aj . Substituting Ai for Aj , the result is
uv 1 xy 1 z, uv 2 xy 2 z, etc. The tree is shown below.
not CF:
1.Some p must exist
indicating the maximum yield
and length of parse-tree.
2. Pickup w , breakup it into
uvxyz, such that |vxy | ≤ p,
|vy | ̸= ε,
3. We win by picking i, and
showing that uv i xy i z ∈
/ L.

To show that a language is

kr chowdhary

TOC

5/ 8

Pumping Lemma for CFLs . . .

Informally, the pumping lemma for CFLs states that for sufficiently
long strings, we can find two, short nearby substrings, that we “can
pump”in tandom, and resulting string must also be in the language.
The pumping lemma states that w can be decomposed into five
substrings. And, two substrings v , y or one of them can be pumped
arbitrary times, and the language strings are still recognized.
The finite languages, which are regular, and hence context-free,
obey the pumping-lemma trivially by having p equal to the
maximum string’s length in L plus one.

kr chowdhary

TOC

6/ 8

Application of Pumping Lemma for CFL
Example: Show that L = {ap b p c p |p ≥ 0} ∈
/ CFL.
Assume that L is CFL, to contradict later, Let p is pumping length
of L. Let w = ap b p c p ∈ L.
The pumping lemma tells us that w can be written as w = uvxyz,
where u, v , x, y , z are substrings of w .
As per theorem. |vxy | ≤ p, |vy | ≥ 1, and uv i xy i z ∈ L. for all i ≥ 0.
By the fact that |vxy | ≤ p, it can be seen that vxy can be contain
no more than two distinct letters. The possibilities are;
1. uxy = aj , for some j ≤ p
2. vxy = b j , for some j ≤ p
3. vxy = c j , for some j ≤ p
4. vxy = aj b k , for some j + k ≤ p
3. vxy = b j c k , for some j + k ≤ p
for each case, it can be easily vaerified that uv i xy i z does not contain
equal numbers of each letter for any i ̸= 1. Thus, uv 2 xy 2 z does not
have the form ai b i c i . Hence, the contradiction, and L ∈
/ CFL.
kr chowdhary

TOC

7/ 8

Bibliography

Chowdhary, K.R. (2025). Normal Forms of Context-Free Grammars.
In: Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_7

kr chowdhary

TOC

8/ 8