.{5} would match any string of 5 symbols (excluding newline). Suppose I wanted to define "a 5-character repetition of a single character."

The immediate way that comes to mind is (.)\1{4}, but this relies on a back reference.

Using a subset of regex which is dependent only on |,(),*,concat any regex expression of pattern size M and search string size N can be solved with a means an M-size NFA in O(NM) time.

Backreferences, unlike +, {n}, etc. are not derivable from the restricted regex tools above, and result in exponential times.

Is it possible to replicate the desired pattern in the non-exponential-time subset of regex (without using exponential* size)? If not, then why (how can we prove so)?

*one could go factorial in size by brute-forcing in this case.

  • $\begingroup$ the pattern .{r5} would expand into a 5*n NFA where n is the size of the alphabet, it would quickly get out of hand $\endgroup$ – ratchet freak May 17 '14 at 2:31
  • $\begingroup$ @ratchetfreak I suspected that was the case (see my note*). How can you prove that that is the case? $\endgroup$ – VF1 May 17 '14 at 3:01
  • $\begingroup$ Without being able to refer to a previous element in an expression, you can't match a group of the same element without brute forcing it. $\endgroup$ – Blrfl May 17 '14 at 3:26
  • $\begingroup$ \1 is not backtracking but backrefrencing. You can make it without backtracking: (.)\1{10} on string aaaaaaaaaaa takes 3 steps, however (.)(?1){10} takes 22 steps to match. $\endgroup$ – revo May 17 '14 at 8:38

Using backreferences you can accept non-regular languages such as the language of squares $ww$, which is accepted by (.*)\1. This language cannot be represented as a non-extended regular expression at all.

  • $\begingroup$ Why not? (It certainly makes intuitive sense, but that's not enough...) $\endgroup$ – VF1 May 17 '14 at 18:30
  • $\begingroup$ That's a standard exercise. You can prove it using the pumping lemma or using Myhill–Nerode. $\endgroup$ – Yuval Filmus May 18 '14 at 5:34

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.