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

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Prime
AI Thread Summary
The discussion focuses on proving that the language L={a^k, k is a prime} is not context-free using the pumping lemma. The initial approach involves manipulating the word s^p and analyzing the implications of adding i|vy| to its length, leading to the conclusion that not all resulting numbers can be prime. Key points include the realization that if p is prime and |vy|>1, then p(1+|vy|) cannot be prime, as it factors into two numbers greater than one. Participants also clarify misunderstandings about the pumping lemma and the nature of prime gaps. Ultimately, the proof's structure is affirmed, with suggestions for clearer presentation.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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??
 
Technology news on Phys.org
evinda said:
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

evinda said:
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.
 
Evgeny.Makarov said:
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...
 
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.
 
Evgeny.Makarov said:
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.
 
I think this works. Very well! But I have several remarks about the presentation.

evinda said:
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$?

evinda said:
and said that if we add $i|vy|$ at the length of $s$
I don't understand the phrase "add ... at the length of ...".

evinda said:
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.

evinda said:
and $|vy|>1$
The variant of the lemma from Wikipedia only says $|vy|\ge1$.
 
Evgeny.Makarov said:
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! :)
 
Back
Top