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.

  • $\begingroup$ Not sure if this helps: mathoverflow.net/a/131909/31729. $\endgroup$
    – copper.hat
    Feb 2, 2015 at 16:38
  • $\begingroup$ 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. $\endgroup$ Feb 2, 2015 at 16:44

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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