Any grammar for the language $L =a^p$, $p$ is prime number of $\mathbb{N}$

Question

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?

Answer 1

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

Answer 2

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.