9
$\begingroup$

I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like |||||||| where the number of | is prime. I immediatly told him that won't ever work because if such a language was regular, the translation of pumping lemma would gives the fact that for a prime $p$ large enough, it exists $k \leq p$ such that $p + nk$ is prime for all $n \geq -1$, and well this is not likely to be the case at all (repartition of primes, triviality of such an unknown and crushing property, ...)

But then someone came with the solution : NOT MATCHING (||+?)\1+ This expression tries to match the capture group (that can be ||,|||,|||| and so on of $k \geq 2$ occurences of |) $n \geq 2$ times. If it matches, it means that the number represented by the string is divisible by $k$, and hence is not prime. Otherwise, it is.

And I felt stupid, because it became obvious that grouping and backreference allows regex to be actually a lot more expressive than...regular expression, in the theoritical sense. Now they even added lookarounds and other operators I didn't know about when I used to do real regex.

According to Wikipedia, it is even more expressive that languages generated by a context-free grammar. So here is my question :

  • can we represent any algebraic language (generated from a context-free grammar) with modern regular expression engines
  • is there a more general description, or at least an upper bound on the complexity of what kind of languages can be described by a modern regex ?

More pragmatically, is there any serious theory behind it or are we just adding any new features as it comes each time it seems implementable to the initial block of real regular expressions based on finite automata ?

I know that "modern regex" isn't very specific while the question is, but I mean at least with backreferences, and possibly more. Of course, if you have partial anwsers assuming certain restrictions on this "modern regex" language, feel free to post it.

$\endgroup$
  • 1
    $\begingroup$ Related question. I seem to remember that at least some RegExp flavors are Turing complete. This article may be a valid starting point for literature research. $\endgroup$ – Raphael Apr 22 '14 at 15:53
  • $\begingroup$ @Raphael thanks a lot, the article seems to answer to a large part of my interrogations $\endgroup$ – yago Apr 22 '14 at 16:01
  • $\begingroup$ Another related question. $\endgroup$ – Raphael Feb 5 '15 at 8:11
  • $\begingroup$ A stronger reason for why not all p+nk can be prime is that when n=p, you have p+nk=p(1+k). $\endgroup$ – Nathan FD Oct 25 '15 at 20:36
3
$\begingroup$

The word problem of regular expressions with backreferences is NP-complete; citing Aho (1990) via Blaisorblade/Charles Stewart.

I don't know the whole set of operators some flavors of regexps have, but several are no more powerful than regular; they have probably been added as syntactic sugar.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.