3,960 views
4 votes
4 votes
  • Prove $a^{2n}: n>0$ is regular using pumping lemma. 

But I am ending up with a prove that this language is not regular as follows. Point my mistakes out. 

Let $w = a^{2n}$ where $n\geq m$, a positive integer. If $xyz$ is a decomposition then clearly -

$y= a^{k}$ with $1\leq k \leq m$.

Now, setting $i=0 \space in \space y^{i}$, we get $w_{0} = a^{2n-k}$, Now as you can see, $w_{0} \notin L$ for odd $k$. Hence the given language is not regular.

3 Answers

Best answer
8 votes
8 votes

Is this language regular?

  1. Yes: Then we can never use pumping lemma for the proof
  2. No: Pumping lemma can be used.

This means that some languages obey pumping lemma but are still not regular. 

Now, coming to the question, here in $w = xyz$, $y = a^k$ is taken. But pumping lemma says there exist "some such y". So, we cannot choose our own $y$ and make it violate pumping lemma. Take $y=a^{2k}$ and it obeys pumping lemma. We have to ensure no such "y" exist which obeys pumping lemma to prove that a language is not regular. 

selected by
1 votes
1 votes
well according to pumping lemma if a language is finite it will be Regular...if the language is infinite and we cannot find any pattern to put into loop during finite representation then it will be definitely not regular...But if somehow we can find a pattern then it may or may not be regular.

as you can see the definition; a^(2n) , 2n is in AP and it is a pattern to put into loop...but it doesn't ensure that language will be regular..Pumping lemma can only say whether a language is not regular...
1 votes
1 votes

$\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.

 

 

edited by

Related questions

0 votes
0 votes
1 answer
3
shallowfalcon asked Oct 17, 2022
425 views
If L = { x == y | where x and y are equal binary numbers} and Σ = {0, 1, =}How can I prove that L is not a regular language using pumping lemma and contradiction?
0 votes
0 votes
0 answers
4
aambazinga asked Sep 9, 2018
407 views
What exactly does it means when we say that a particular string can be pumped or not in pumping lemma?,,.. and consequently what is the pumping length for a regular langu...