- http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_langu...
We are all running computers that are finite-state machines: if you have roughly a trillion bits of storage, you can have up to 2^1T states.
For most numbers that are interesting to humans, we are able to test their primality with regular languages, which are detectable by finite-state machines. The number of states might be quite large indeed.
However, I must disagree that we are able to use regular expressions to test for primality all the number we're interested in. Your argument only proves that there exists a regular expression that tests for primality all the numbers below N, where N is arbitratily large. It does not shows any way how to construct it, nor does it guarantee that the DFA we will be using to test for primality will fit in available memory.
 - http://news.ycombinator.com/item?id=3046623
 - It's actually trivial: example regular expression we're looking for is /a^p_1|a^p_2|...|a^p_N/, where p_1, ..., p_N are primes below. Sadly, to use it to test for primality, we need to know if the number is prime beforehand.
Actually, it sounds like an interesting problem -- to come up with an interesting and nontrivial regular expression schema that for every N gives us a regular expression that tests for primeness all numbers less than N.
Come to think of it, the existence of any such interesting schema seems highly unlikely -- the Parikh's theorem implies that the set of lengths of words matched by regular expression (or even context-free grammar) seems to be too constrained to allow for such scheme -- we can easily find non-prime matched by an such regular expression, and Parikhs theorem seems to imply that it is not much bigger than the automaton state count.
The amount of storage of a computer is not fixed, and is easily extendable, and extending memory fits simply in the Turing Model, and does not affect the internal states of the Turing Machine. In contrast, any time a new source of memory is introduced (say, a new hard drive or aws cluster), you'd have to change your DFA, which breaks your statement 'a computer is a DFA'.
I really don't see how calling computers DFA's can in anyway be considered 'practical'.
I don't think that solution would be very feasible anyway. The four largest known primes alone would take about 20 megabytes if stored as unsigned integers.
And you can get similarly informed comments in Reddit, Slashdot, heck, with enough eyes reading a thread even CNET...
One common regular expression extension that does provide additional power is called backreferences. A backreference like \1 or \2 matches the string matched by a previous parenthesized expression, and only that string: (cat|dog)\1 matches catcat and dogdog but not catdog nor dogcat. As far as the theoretical term is concerned, regular expressions with backreferences are not regular expressions. The power that backreferences add comes at great cost: in the worst case, the best known implementations require exponential search algorithms, like the one Perl uses. Perl (and the other languages) could not now remove backreference support, of course, but they could employ much faster algorithms when presented with regular expressions that don't have backreferences, like the ones considered above.
If that and the Wiki article still don't help you understand why regexp != regular expression, please ask. =]
That's Perl built-in job security right there. Also why I don't use it except as throw-away scripting at the bash prompt:)
Huh? You mean, this is about Perl because regexps was created in Perl and the Perl regexp lib isn't ported anywhere else?
(If you must troll, at least be interesting. :-( )