# Pumping Lemma

Pumping lemma is used to prove that a language is not regular. To prove this the following three conditions must satisfy:

- xyiz where i≥0
- |y|>0
- |xy|≤P

Let us consider an example A={yy/y€{0,1}* }

**Proof:** we know that * is closure operation over symbols 0,1.

Assume that A is regular and it must have Pumping length P. let us consider the string S=0101 and consider the value of P=7. We can assume the value of P as per our choice. But the trick is while choosing the value of P always see the third condition of Pumping lemma i.e |xy|≤P . therefore the value of P is in such a way that the combination of x and y must be equal or less than that of P. let us see the example for more clarify the concept:

S=0p10p1 (we can also write it as 01p01p)

Let P=7

Divide the string S into three parts:

00/x 0000/y 0100000001/z (according to the trick we divide the string in a way of |xy|≤P)

Now see the first condition xyiz where i≥0

Let us consider i=2 xyiz => xy2z => x=00

y=0000

y2=00000000

z=0100000001

⸫ xy2z =00000000000100000001

⸫ xy2z ≠A

|y|≥0 and |xy|≤P i.e 000000≤7

Hence , A is not a regular language as the three conditions are true.

Written by:

Deepika Bhatia