A regular expression to check for prime numbers (2007)

No. The wikipedia page has an example of a pumpable but non-regular language. You just need to take the union of a pumpable language and a non-regular language in a way that you can pump elements of the second into elements of the first. The Wikipedia example is a little more formal, but we can do something like this.

Consider, over the binary alphabet,

L1 = {s : 00 or 11 is a (consecutive) substring of s}

L2 = {(01)^n : n represents a Turing machine that halts on the empty tape}

and L = L1 union L2. Identifying elements of L2 is "difficult" (this is where I'm not being formal, but clearly this is beyond the power of regular languages) and the elements of the two languages are disjoint (so I'm not playing some tricks with my language secretly being Σ*).

Take the pumping length p = 3. There are only eight possibilities for the first three characters: 000,001,010,011 and their bitwise complements. In the first two cases pump on the last character as any string starting 00 is in the language L. In the third case pump on the middle character; either we get repeated 1s or the zeroes coalesce (note that this is exactly where we collapse L2 into L1 by pumping it). In the last case, pump on the first character; the repeated 1s ensure the final string is in L. For the complements just complement my constants.

So any string s in L can be pumped. But it's clear that no DFA is going to recognize L2, a disjoint language from L1. I use the halting problem for L2 as a "hard problem" but you can just choose an arbitrary other language L2 = {(01)^n : n encodes an element of L*, where L* is not regular}.

1. Assuming the language is regular, the pumping lemma tells us that it has a pumping length m, and all strings of length at least m can be divided into a prefix x, a suffix z, and a pumpable substring y, such that:

1a. |xz| < m

1b. |y| > 1

1c. The concatenation x y^n z remains in the language for all n. (In this case, this means that |xz| + n*|y| is nonprime for all nonnegative y.)

2. Consider the string c = 1^p², where p is a prime number greater than m[1].

3. The pumping lemma will divide c into substrings x y z as described above.

4. Observe that |xz| < m < p and |y| = p² - |xz|

5. Dirichlet's theorem tells us that the arithmetic sequence {a + nd} contains infinitely many primes as long as a and d are coprime. Pumping our string c will generate strings with lengths belonging to the arithmetic sequence {|xz| + n(p² - |xz|)}. It remains to be shown that |xz| and (p² - |xz|) are coprime.

6. Observe that any number which divides both (p² - |xz|) and |xz| will also divide [(p² - |xz|) + |xz|] = p².

7. Since p is prime, the only divisors of p² are 1, p, and p².

8. Since |xz| < p, we can see that gcd(|xz|, (p² - |xz|)) = 1.

This completes the proof; pumping c is guaranteed to produce not just one but infinitely many strings of prime length.

[1] Euclid tells us that there is no greatest prime number, so we can guarantee the existence of such a p.

Sure some people might say "thou" is archaic, however so is using "regex" outside of academic contexts to mean regular languages. I don't see how one could justify one but not the other.

The current state of a human language is defined by common usage. The purpose of a language is for people to be able to communicate ideas. Ideas exist all up and down a specificity spectrum, e.g. “regex” might mean a specific syntax or one of several syntaxes depending on context. Kind of like “kleenex” might refer to a specific brand or to the general concept of tissue.

If 99.9% of people successfully (by their own measure, not yours) communicate what they mean when they use the term “regular expression”, but you are among the 0.1% for which that interaction fails, then I would argue that the problem is your pedantry, not the term. I’m not saying this to be mean; I have similar issues.

There's some kind of idea going around that because the plural of "ox" is "oxen", plurals with -n must be triggered by a word ending in "x". So you see cutesy references to "boxen" or similar.

But -n is just an ordinary plural marker; the same ending that makes "oxen" the plural of "ox" also makes "kine" the plural of "cow" and "children" the plural of "child". (In those last two cases, the words are sporting two plural markers in sequence.)

And yeah, they’re faster because they can be statically compiled to the point of running strings “through” the expression rather than running the expression “on” the string, so to speak. (i.e as an FSM, iterating char by char the operations boil down to purely compare and branch to known destinations)

Anyway, real REGUALR expressions belong to the regular languages class, thus equivalent to DFAs. Given a regexp, you can construct a DFA in O(2^n), where n is the number of operators in the regexp. Now this DFA will have a Linear time complexity match. If you extend regular expressions with backreferences, you can't build DFAs anymore, and you also lose the fundamental property of regularity: the pumping lemma for regular languages. Furthermore, the languages you can build with this extension go even outside the context-free class. Not only that: you are also dealing with an NP-complete matching. Again, why do you still call them regular?

If state-space explosion is a concern, you can implement a non-backtracking regular expression matcher using term rewriting. For true regular expressions, the size of the rewritten terms are a function of the size of the pattern (and thus performance is linear). For non-regular expressions, this does not hold.

-> there exists a integer N such that pumping lemma holds for any w in L longer than L. (That is we can divide w into xyz and pump y, where |xy| ≤ n, and y is nonempty).

-> now consider a^N b^N, we cant divide it into xyz such that we can pump y and w still remains in a^n b^n.