# Formal Grammar generating $0^p$

Exercise: Find the formal grammar generating the language ${0^p}$ in the binary alphabet for $p$ prime.

I have absolutely no clue where to start, nothing of the 'usual' construction strategies seem to work. It cannot be 'factored' as a concatenation of smaller alphabets, not written as a finite union of simpler ones, not as a finite intersection of simpler ones. Also prime numbers are so randomly distributed that I can hardly believe this really is generated by a formal grammar.

A rather elementary observation that can be made, is that this language is not context free. This is proved with the pumping lemma for context free languages.

Any help highly appreciated.

• Not sure if this helps: mathoverflow.net/a/131909/31729. Feb 2, 2015 at 16:38
• Already saw that, thanks. The way the question is formed however, there should be a rather 'nice' description, just postulating the existence by writing that the existence is guaranteed since it is decidable, is not quite what the exercise seems to be pointing towards. Feb 2, 2015 at 16:44