Trick to Solve Pumping Lemma

Pumping Lemma

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

1. xyiz where i≥0
2. |y|>0
3. |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:
[insert_php]
echo the_author_posts_link();
[/insert_php]