Search code examples
mathprimesdfanfa

Can you make a DFA/NFA/ Lambda NFA for determining whether a number is prime or not?


As the title says, is it possible?


Solution

  • No, this isn’t possible. There are several ways you can encode “the set of all prime numbers” as a language, and the standard ways of doing so (writing the number out in binary, writing out a number of tally marks equal to the number, etc.) aren’t regular.

    Formally proving this is a bit tricky but is doable using either the pumping lemma for regular languages or the Myhill-Nerode theorem. The crux of the arguments boil down to the fact that replicating parts of prime numbers repeatedly will eventually give you a non-prime number, and that’s where the technical details of the proofs come in.

    Hope this helps!