Pumping Lemma for Regular sets, Problems Based on Pumping Lemma


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.

Custom Search

%d bloggers like this: