{a^k,k is a prime is not contextfree}

[evinda]

Hi! :) I have to show that the language $L=\{a^{k},\text{ k is a prime }\}$ is not context-free..I thought that I could show this,using the pumping lemma.I took the word $s^{p}$,and said that if we add $i|vy|$ at the length of $s$,it must still belong in $L$..To show that it is not possible,I said:for i=|vy|,we have $p+i|vy|=p+|vy|^{2}=k$ ,if we take i=|vy|+1,we have $p+i|vy|=k+|vy|$.Some of the prime numbers are:2,3,5,7,11,13,... so we see that the difference of one prime number from the next one is greater or equal to one...So,if $p+(|vy|+1)|vy|$ was the next prime after $p+|vy|^{2}$,$|vy|$ should be greater than one,something that is not given from the pumping lemma.So,the first condition is not satisfied and so we conclude that the language is not contextfree...Could you tell me if I can explain it like that??

 

[Evgeny.Makarov]

so we see that the difference of one prime number from the next one is greater or equal to one...

What would be the alternative: that the difference between one prime number and the next one is zero? :D

So,if $p+(|vy|+1)|vy|$ was the next prime after $p+|vy|^{2}$,$|vy|$ should be greater than one,something that is not given from the pumping lemma.

In fact, it is given by the lemma; see point 2 here. More importantly, if the lemma does not state something explicitly, it does not follow that it is false.

 

[evinda]

What would be the alternative: that the difference between one prime number and the next one is zero? :D

In fact, it is given by the lemma; see point 2 here. More importantly, if the lemma does not state something explicitly, it does not follow that it is false.

Ok,I understand...

 

[Evgeny.Makarov]

The idea is to prove that an arithmetic progression cannot consists entirely of prime numbers. This requires a bit of ingenuity, but it is possible to construct a member of the progression that definitely factors into two numbers greater than one.

 

[evinda]

The idea is to prove that an arithmetic progression cannot consists entirely of prime numbers. This requires a bit of ingenuity, but it is possible to construct a member of the progression that definitely factors into two numbers greater than one.

Could I show it maybe like that?

If we add $i|vy|$ at the length of $s$,it must still belong in $L$.
So $p+i|vy|$ must be a prime number for each $i \geq 0$. For $i=p$ we have $p+p|vy|=p(1+|vy|)$. $p$ is a prime greater than 1 and $|vy|>1$, so $ p(1+|vy|)$ is not a prime since it is written as a product of two factors greater than 1.

 

[Evgeny.Makarov]

I think this works. Very well! But I have several remarks about the presentation.

I have to show that the language $L=\{a^{k},\text{ k is a prime }\}$ is not context-free..I thought that I could show this,using the pumping lemma.I took the word $s^{p}$

What is $s$ and what is $p$?

and said that if we add $i|vy|$ at the length of $s$

I don't understand the phrase "add ... at the length of ...".

So $p+i|vy|$ must be a prime number for each $i \geq 0$. For $i=p$ we have $p+p|vy|=p(1+|vy|)$. $p$ is a prime greater than 1

Why is $p$ prime? In fact, whether $p$ is prime is irrelevant for the rest of the proof.

and $|vy|>1$

The variant of the lemma from Wikipedia only says $|vy|\ge1$.

 

[evinda]

I think this works. Very well! But I have several remarks about the presentation.

What is $s$ and what is $p$?

I don't understand the phrase "add ... at the length of ...".

Why is $p$ prime? In fact, whether $p$ is prime is irrelevant for the rest of the proof.

The variant of the lemma from Wikipedia only says $|vy|\ge1$.

Nice..thank you! :)