-1
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Apr 26, 2013 at 5:38
  • $\begingroup$ @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. $\endgroup$ Apr 26, 2013 at 8:37
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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