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?
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? 


$L$ is not context free, so has no contextfree grammar describing it, but it is decidable, so there is an unrestricted grammar for it (there should also be a contextsensitive 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$. 


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

