**Pumping lemma** is used to prove that a language is NOT REGULAR.

It cannot be used to prove that a Language is Regular.

If A is a Regular Language, then A has a Pumping Length 'P'such that any string 'S'where |S|≥P may he divided into 3 parts S=xyz such that the following conditions must be true:

1. x y z^i∈ A for every i≥0

2. |y|>0

3.|xy|≤P

To prove that a language is not Regular using PUMPING LEMMA, follow the below steps:

(we prove using Contraction)

1. Assume that A is Regular

2. It has to have a Pumping Length(say P)

3. All strings longer than P can be pumped |S|≥P

4. Now find a string 'S' in A such that |S|≥P.

5. Divide S into x y z.

6. Show that xy^iz∉A for some i.

7. Then consider all ways that S can be divided into x y z.

8. Show that none of these can satisfy all the 3 pumping conditions at the same time.

9. S cannot be Pumped == CONTRADICTION.

**Problem:**

Using Pumping Lemma Prove that the language A={a^n b^n| n≥0} is NOT REGULAR.

**Solution:**

Assume A is Regular

and Pumping length is P.

So, S=a^p b^p

Let p=7

Then,

S=aaaaaaabbbbbbb

Now taking different cases.

Case 1: If Y is in 'ä' part

Let x→(aa)

y→(aaaa)

z→(abbbbbbb)

Case 2: If Y is in 'b' part

Let x→(aaaaaaabb)

y→(bbbb)

z→(b)

Case 3: If Y is in both 'a' and 'b' part

Let x→(aaaaa)

y→(aabb)

z→(bbbbb)

Now lets check the condition 1 for all the cases:

In Case 1: xy^iz=xy^2z(let i=2)

aaaaaaaaaaabbbbbbb

a≠b

11≠7

In Case 2: xy^iz=xy^2z(let i=2)

aaaaaaabbbbbbbbbbb

a≠b

7≠11

In Case 3: xy^iz=xy^2z(let i=2)

aaaaaaabbaabbbbbbb(not in the form a^n b^n)

So, none of the cases satisfies condition 1.

Also, condition 2(|xy|≤p, p=7) is not satisfied by case 2 and 3.

So, none of these case satisfies all 3 conditions hence, it contradicts that A is a Regular Language.

**Note:-** For any doubt or question you can comment below.