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 = a

^{k}b

^{k }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 = a
^{n}b^{n}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, uv
^{m}w ∈ L. - Since |v| > 0, v has at least one symbol.
- Also since |uv| ≤ n, v = a
^{p}, for some p > 0, - Let us now consider the string uv
^{m}w for m = 2. - Then uv
^{2}w = a^{n-p}a^{2p}b^{n}= a^{n+p}b^{n}. Since p > 0 , n + p ≠ n . - Hence a
^{n+p}b^{n}can not be in the language L represented by a^{k}b^{k}. - This violates the condition that for every m ≥ 0, uv
^{m}w ∈ 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 : uv
^{k}wx^{k}y ∈ 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!**

## Comments

write a commentPankaj SharmaDec 30, 2016

Shyam VermaApr 20, 2017

Shriya SinghSep 19, 2017

so, sir plz tell me that how to solve it??

...Read MoreBalajirao MahendrakarSep 20, 2017

...Read MoreVarun MahanotSep 21, 2017

Vipin Kishor KujurJun 15, 2019

@Mallesham DevasaneI need your help & suggestion, I did Computer Science Engineering but I want to prepare for ESE(EC) ,Please guide me...Read MoreAnjali GairolaApr 19, 2020

Anjali GairolaApr 19, 2020

PreetiJul 11, 2020

Behave

PreetiJul 11, 2020

Behave the