## Pumping lemma

It is used to prove that a language is not regular. It cannot 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 be divided into three parts S=xyz such that the following conditions must be true :

i. xyiz where i≥0

ii. |y|>0

iii. |xy|≤P

To prove that a language is not regular using Pumping Lemma, follow the below steps:

1. Assume that A is regular language.

2. It has to have Pumping lemma say P.

3. All strings longer than P can be Pump i.e |s|≥P.

4. Divide S into xyz i.e in three parts.

5. Show that xyiz not belongs to A for some i.

6. Then consider all base that x can be divided into xyz.

7. Show that none of these conditions can satisfy Pumping lemma at the same time.

8. S cannot be Pump=Contradiction.

Example: using Pumping Lemma prove that a language A is not regular.

A={anbn n≥0 }

Solutions:

1. assume that A is regular language.

2. Assume that A is having Pumping lemma P.

3. Consider string S= apbp having pumping length P=7. [anbn=apbp i.e n=p]

4. Therefore string becomes S= aaaaaaabbbbbbb.

5. Divide S into three parts i.e xyz.

Case 1: The y part may be lie in a.

aa/x aaaaa/y bbbbbbb/z

case 2: The y part may be lie in b.

aaaaaaa/x bbbb/y bbb/z

case 3: The y part may be lie in a and b.

aaaa/x aaabb/y bbbb/z

now we have to prove all cases wrong according to the three conditions written above:

Prove case 1 wrong:

xyiz let i=2 =>xy2z =>x=aa , y=aaaaaaaaaa (after solving y2),z=bbbbbbb

aa/x aaaaaaaaaa/y bbbbbbb/z

no. of a’s=12 and no. of b’s=7 therefore a≠b , |y|>0

Prove case 2 wrong : xyiz let i=2 =>xy2z =>x=aaaaaaa , y=bbbbbbbb (after solving y2),z=bbb

aaaaaaa/x bbbbbbbb/y bbb/z

no. of a’s=7 and no. of b’s=11 therefore a≠b , |y|>0

prove case 3 wrong: xyiz let i=2 =>xy2z =>x=aaaa , y=aaaaaabbbb (after solving y2),z=bbbbb

aaaa/x aaaaaabbbb/y bbbbb/z

no. of a’s=10 and no. of b’s=9 therefore a≠b , |y|>0

Therefore the language A is not a regular language.