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!
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 :)