News for hackers. Stuff that matters.

A comment on A regular expression to check for prime numbers. Parent comment

Re:A regular expression to check for prime numbers by evanb on Wednesday June 21, 2023 @04:25AM (#36415892)
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

[ Parent | on HN ]
Re:A regular expression to check for prime numbers by aleph_minus_one on Wednesday June 21, 2023 @04:33AM (#36415946)
Via the pumping lemma, you can easily prove that testing whether a number is a prime number cannot be implemented as a regular expression.
[ Parent | on HN ]
Re:A regular expression to check for prime numbers by Tainnor on Wednesday June 21, 2023 @06:28AM (#36416745)
Via the context-free pumping lemma, you can even prove that prime numbers don't form a context-free language either.
[ Parent | on HN ]
Re:A regular expression to check for prime numbers by taejo on Wednesday June 21, 2023 @08:07AM (#36417411)
And via Parikh's theorem, with a one-symbol alphabet, regular and context-free languages are the same.
[ Parent | on HN ]