Pumping lemma for regular languages

 Pumping lemma to prove that a certain language is not regular language.Pumping lemma was introduce by Yehoshua Bar-Hillel in 1961. If  A is a regular language then A has a pumping length 'P' such that any string 'S' where |S|>=P may divided into 3 parts S=xyz and condition are:

• xyⁱz ε A for every i>=0.

• |y|>0.

• |xy|<=P

TO prove that a language is not regular using pumping lemma.

let assume A is regular.

It has to have a pumping length P.

All strings longer than P can be pumped |S|>=P.

Now find a string 'S' in A such that |S|>=P

Divide S into xyz.

Show that xyⁱz ∉A for some i.

Consider all way that S can be divided into xyz.

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

S cannot be pumped(Contradiction).

So using pumping lemma prove that language is not regular by contradiction.

Example 

Using pumping lemma prove that the language A=aⁿbⁿ   n>=0  is not Regular.

Solution:  Assume A is regular.

pumping length=n

S=aⁿbⁿ 

Let p=7

S=xyz

S=aaaaaaabbbbbbb

Case1: The y is in the 'a' part

S=aaaaaaabbbbbbb

Sis divided into three parts.

let assume x=aa

                  y=aaaa

                  z=abbbbbbb

Now pump the value of y.

xy²z

aa aaaaaaaa abbbbbbb

now check this string lie in our language A or not.

No of a =11

no of b=7

Number of a  and number of b are not equal. but in our language number of a equal to the number of b.So this string not lie in our language.

Case2: The y is in the 'b' part

S=aaaaaaabbbbbbb

Sis divided into three parts.

let assume x=aaaaaaabb

                  y=bbbb

                  z=b

Now pump the value of y.

xy²z

aaaaaaabb bbbbbbbb b

now check this string lie in our language A or not.

No of a =7

no of b=11

Number of a  and number of b are not equal. but in our language number of a equal to the number of b.So this string not lie in our language.

Case3: The y is in the 'a' and 'b' part

S=aaaaaaabbbbbbb

Sis divided into three parts.

let assume x=aaaaa

                  y=aabb

                  z=bbbbb

Now pump the value of y.

xy²z

aaaaa aabbaabb bbbbb

now check this string lie in our language A or not.

aaaaa aabbaabb bbbbb  it is not following  aⁿbⁿ   pattern. this also does not lie our language.

All the three case string does not lie our language.

 xyⁱz ∉A  that does not follow the first condition  of  regular language . 

|xy|<=P  is the second condition of regular language. but here length of p=7 and xy=13 in case2 

13 is not less than or equal to 5. So not follow the second condition of regular language.

So  condition not satisfy. So that is proof  aⁿbⁿ   is not regular by contradiction. So using pumping lemma prove language is not regular.