3 ms·

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 3y ago
  Via the context-free pumping lemma, you can even prove that prime numbers don't form a context-free language either.
  • taejo 3y ago
    And via Parikh's theorem, with a one-symbol alphabet, regular and context-free languages are the same.