Hacker News Reader

Could the AKS primality test, which showed that PRIMES is in P, be implemented as an honest regular expression? Presumably not because then we'd know that PRIMES is not just in P but is a regular language, which would be too good to be true.

https://en.wikipedia.org/wiki/AKS_primality_test

View on HN

Via the pumping lemma, you can easily prove that testing whether a number is a prime number cannot be implemented as a regular expression.

Via the context-free pumping lemma, you can even prove that prime numbers don't form a context-free language either.

And via Parikh's theorem, with a one-symbol alphabet, regular and context-free languages are the same.

Reply on news.ycombinator.com