A regular expression to check for prime numbers

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 ]