No, the point is that the article does not use a real regular expression: 1. Real regular expressiona can always be checked in linear time 2. primes can not be checked in linear time Ergo: primes can not be checked with regular expressions, otherwise there would be a way to check primes in linear time, which would contratict premise 2