Study Notes of Pumping Lemma

By Mukesh Kumar|Updated : December 3rd, 2021

Pumping Lemma for regular languages

  • Suppose that a language L is regular. Then there is a FA that accepts L.
  • Let n be the number of states of that FA. Then for any string x in L with |x| ≥ n, there are strings u, v and w which satisfy the following:
    • x = uvw
    • |uv| ≤ n
    • |v| > 0 is same as v ≠ ε
    • For every integer m ≥ 0, uvmw ∈ L.
  • If L is regular then for every x such that |x| ≥ n then there exists uvw such that x=uvw, v ≠ ε, |uv| ≤ n, and for which uviw is in L for every i.


Pumping Lemma gives a necessity for regular languages.

Pumping Lemma is not sufficient, that is, even if there is an integer n that satisfies the conditions of Pumping Lemma, the language is not necessarily regular.

Pumping Lemma can not be used to prove the regularity of a language.

It can only show that a language is non-regular.

Example: L = akbis non-regular, where k is a natural number.
  • Suppose that L is regular and let n be the number of states of an FA that accepts L. Consider a string x = anbn for that n.
  • Then there must be strings u, v, and w such that
  • x = uvw, |uv| ≤ n |v| > 0, and for every m ≥ 0, uvmw L.
  • Since |v| > 0, v has at least one symbol.
  • Also since |uv| ≤ n, v = ap, for some p > 0,
  • Let us now consider the string uvmw for m = 2.
  • Then uv2w = an-pa2pbn = an+pbn. Since p > 0 , n + p ≠ n .
  • Hence an+pbn can not be in the language L represented by akbk.
  • This violates the condition that for every m ≥ 0, uvmw L.
  • Hence L is not a regular language.

Pumping Lemma for CFL’s

  • Let L be a CFL. Then there exists a constant N such that if z L s.t. |z|≥N, then we can write z=uvwxy,
  • |vwx| ≤ N
  • vx ≠ ε
  • For all k ≥ 0 : uvkwxky L

You can follow the detailed champion study plan for GATE CS 2021 from the following link:

Detailed GATE CSE 2021 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series!(100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering


The Most Comprehensive Exam Prep App!

Download BYJU'S Exam Prep app for Exam Preparation here

Posted by:

Mukesh KumarMukesh KumarMember since Feb 2020
Share this article   |


write a comment
Load Previous Comments
Pankaj Sharma
Language is regular
Shyam Verma

Shyam VermaApr 20, 2017

Pumping is used to prove certain languages non-regular only..
Shriya Singh

Shriya SinghSep 19, 2017

The language L={a^n b^m|m,n>=0} is a regular language but when I apply pumping lemma it comes as non regular.
so, sir plz tell me that how to solve it??
...Read More
Balajirao Mahendrakar
Sir... I completed in machine design specialisation..but not showing in gate application ...Which specialisation i am choose... Please clarify my doubt...
...Read More
Varun Mahanot
Can we choose an odd or even n while using pumping lemma theorem??
Vipin Kishor Kujur
Sir @Mallesham Devasane  I need your help & suggestion, I did Computer Science Engineering but I want to prepare for ESE(EC) ,Please guide me
...Read More

PreetiJul 11, 2020


PreetiJul 11, 2020

Behave the

Follow us for latest updates