You're mostly right, I made a similar point few months ago[1].
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[2], nor does it guarantee that the DFA we will be using to test for primality will fit in available memory.
[2] - 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.
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[2], nor does it guarantee that the DFA we will be using to test for primality will fit in available memory.
[1] - http://news.ycombinator.com/item?id=3046623
[2] - 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.