Via the pumping lemma, you can easily prove that testing whether a number is a p... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		aleph_minus_one on June 21, 2023 \| parent \| context \| favorite \| on: A regular expression to check for prime numbers (2... Via the pumping lemma, you can easily prove that testing whether a number is a prime number cannot be implemented as a regular expression.

Tainnor on June 21, 2023 [–]

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

taejo on June 21, 2023 | [–]

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

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact