It's also worth noting that what this expression matches are not primes given in decimal notation; rather, the language it accepts is "111...111" with any prime

It's also worth noting that what this expression matches are not primes given in decimal notation; rather, the language it accepts is "111...111" with any prime number of 1s. And we know straight-up that no "true" regular expression matches this language, by the pumping lemma (http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_langu...).