$\color{Red}{\text{Understand Complete Pumping Lemma, Crystal Clear:}}$
Here is Complete Pumping Lemma Lecture: https://youtu.be/8cdPjuYbIrU
This Pumping Lemma lecture contains EVERYTHING about Pumping Lemma of Regular Languages, i.e. Proof, Examples, Variations, GATE PYQs, Finding minimum pumping length etc. Watch this lecture for Complete, Correct & Clear Understanding.
Pumping lemma for Regular languages says
" If a language L is Regular,
then $\exists P \geq 1$, such that
$\forall \,\,strings\,\,w \in L$, Where $|w| \geq P$
$\exists x,y,z$, such that $w = xyz$
and $|xy| \leq P$
and $y \neq \in$ i.e. $|y| \geq 1$
and $\forall q \geq 0$, $xy^qz \in L$
In Words, If $L$ is regular, then there’s some magic number $P$(Called Pumping length). And if I take any string $w$ that is at least as long $P$, then I can break it up into three parts $x, y, $and $z.$ Now, the length of $xy$ is less than or equal to $P$, and also the length of $y$ is greater than or equal to $1$ and less than or equal to $P$.
NOTE that The first line is If $L$ is regular This means that our theorem only applies if the language is regular. It doesn’t apply if $L$ is not regular. I know you don't agree. But hold on. I'll prove it to you.
People say that We use the pumping theorem to show that a language isn’t regular. And It is indeed True. Then Why did I say the above line??
That's because Pumping lemma is a Proof by Contradiction. In other words, we assume $L$ is regular, then we show that it doesn’t satisfy the pumping theorem. This gives us a contradiction, so our initial assumption that $L$ is regular must be wrong.
So, Now let's consider the given language $L = a^{2n}, n \geq 1$
Let's Assume that $L$ is Regular.
Now, Since we have assumed that $L$ is Regular, so, This means that there’s some ”magic number” $P$ for the language $L$, such that the all the things in the rest of the theorem are true.
So, Let's say $P = a^{2k}$ where $k$ is some Constant. Because $P$ has to be some Fixed value for All the Strings.
So, as Pumping lemma states, For all $w$, where $|w| \geq P$, i.e. Sufficiently Large Strings, $w$ can be split into three Parts $x,y,z$.
So, Let's take some sufficiently large string with $|w| = P$ (as All the Strings with length greater than or equal to $P$ must satisfy the condition... So, $|w| = P$ must also satisfy)
So, Let $w = aaaaaa.........a$ Where $|w| = P$. Now let's try to split $w$ in three parts $x,y,z$ such that $|xy| \leq P$, $y \neq \in$
Since $x$ can be Null, Let me make it Null. So, now $w = yz$, and let me take $y = aa$.
So, Now, So far, I have satisfied All the conditions of Pumping lemma, Now it's time to taste the fruit and see whether it is sweet or bitter.
Now, $\forall q \geq 0$, $xy^qz $ should be in $L$. Let's check if it is or is not.
Since $y = aa$.. Now, Apply $y^0, y^1, y^2,y^3..... and\,\, so\,\, on$..You will see that All these strings belong to the language $L$.
And similarly You can easily check yourself for All the strings $w$ with $|w| \geq P$.
Hint : For this language, You can always(for all sufficiently large strings) take $x = \in$, $y = aa$. And the Pumping lemma conditions will satisfy.
So, Now, We have showed that the Given language Satisfy Pumping lemma for Regular languages. But Pumping lemma is a Proof by Contradiction. In other words, we assume $L$ is regular, then we show that it doesn’t satisfy the pumping theorem. This gives us a contradiction, so our initial assumption that $L$ is regular must be wrong.
But Our language $L$ has satisfied the Pumping lemma, So, We can not say whether or not $L$ is Regular.
