MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Any grammar for the language $$L =a^p,\text{ $p$ is prime and }p\in \mathbb{N}?$$

Is such a grammar related to any question of number theory like RH or the conjecture of twin primes?

share|cite|improve this question
Thank you ,Emil. – XL _at_China Apr 26 '13 at 12:03
up vote 4 down vote accepted

$L$ is not context free, so has no context-free grammar describing it, but it is decidable, so there is an unrestricted grammar for it (there should also be a context-sensitive grammar, but I haven't thought too hard about that).

I can't see why this would have any bearing on number theoretic questions like the Riemann Hypothesis, or the Twin Prime Conjecture, all the $L$ requires is that you are able to count and say whether a number is prime, it gives no information about other numbers, or what numbers might be prime - at least any more than being able to say whether a number is prime or not.

If there is a grammar for $L$ that somehow has bearing on the RH or TPC, it is because it does something extra that this language doesn't need: there is a Turing Machine that decides $L$ by taking an input $a^{m}$, counts $m$ then passes $m$ to a TM that decides whether $M$ is prime, as we don't care about the running time of this machine we can use a simple, but slow method such as repeated attempts at division. As this TM exists, we can convert it into a grammar directly. Thus even though we don't know the precise grammar, we know that this language can be decided without knowledge further than being able to tell if a number is prime.

So there may be a grammar for $L$ that employs a trickier method that would have bearing on other matters, but it's not really anything to do with being able to generate $L$.

share|cite|improve this answer
Obviously,there is a grammar that produce it,But we do not know the grammar. But I am not sure this has bearing on number theoretic questions like RH or TPC,since the grammar may be transformed into algorithm or function which may characterize the set of prime number.Anyway, thank you for your answer. – XL _at_China Apr 26 '13 at 5:38
@XL, I've extended my answer a bit to try an highlight the jump between a grammar that really only generates the language, and one that might have greater number theoretic importance. – Luke Mathieson Apr 26 '13 at 8:37
@Luke,Thank you very much. – XL _at_China Apr 26 '13 at 9:01

There is a trival algorithm checking primality using linear space (on a Turing machine). Thus there is a context-sensitive grammar for this language. However, there is no context-free grammar by a pumping argument.

share|cite|improve this answer
@The User,thank you ,but is there any pumping argument of context-sensitive grammar or language?I think it must be a typo – XL _at_China May 26 '13 at 13:47
It was a typo, I meant “context-free”. – The User May 26 '13 at 15:19
There is a context-sensitive grammar, but no context-free grammar. I have corrected it. – The User May 26 '13 at 15:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.