Formal Grammar generating $0^p$

Question

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.

Answer 1

My better guess is to use a unrestricted grammar. With that you can generate an arbitrary number of 'A', say n and then you check if this number is divisible by any number between 2 and n. My idea to check divisibility is to put spacer 'S' between each group of AA if the last spacer is at the end of the word then the word is not accepted, otherwise we increment the space between the spacer to check divisibility by 3. To increment the space you can do something like increment the first spacer the shift all the others, then increment the second and so on.

You can thus check divisibility for all the number smaller than n and as soon as there is only one spacer left in the word (ie as you checked for divisibility for all number smaller than n/2) you can change all the A by 0 and remove all the other stuff you used.

Sorry, my idea is a bit messy. An easier way to see it is to simulate a turing machine that recognize your language. It may be easier to see what happen ...

If you need more detail please ask. I hope it answers the question.