0

I want to write a grammar which produces binary prime numbers. But I can't find any patterns this grammar can be made of. Like this:

1. In binary all prime numbers except 2 begin and end with 1
2. Concatenation of 2 prime numbers is a prime number (not 100% sure about this...)

If I had a whole set of such rules, it wouldn't be hard to write a grammar. Any information will be valuable for me!

Thank you in advance!

Anton Ostrouhhov
  • 29
  • It would seem there's no context-free grammar whose language is the set of primes (or even an infinite subset of primes), though I don't really understand the proof. This is only a partial answer since maybe the primes could be generated by a more exotic grammar, though I doubt it. – Jack M Nov 10 '18 at 22:43
  • 1
    @JackM Thank you for reply! I am talking about Type-0 and Type-1 grammars (Chomsky hierarchy) which describe Recursively enumerable and Context-sensitive languages. – Anton Ostrouhhov Nov 11 '18 at 06:55

1 Answers1

0

I have not found such a patterns/rules so far... But I found another way to solve this problem.

I wrote Turing Machine which accepts binary primary numbers (GitHub Gist). After that my friend wrote interpreter from TM to Grammar (examples can be found on GitHub). We got about 77000 productions in resulting Grammar. I believe this number can be reduced a lot, but this is another story anyway :)

Anton Ostrouhhov
  • 29