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.
Table of content
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 = akbk is 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
Thanks
The Most Comprehensive Exam Prep App!