Study Notes of Pumping Lemma

By BYJU'S Exam Prep

Updated on: September 25th, 2023

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
Our Apps Playstore
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303
Home Practice Test Series Premium