2
$\begingroup$

.{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.

Improve this question
$\endgroup$
4
  • $\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
    Commented May 17, 2014 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
    Commented May 17, 2014 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
    Commented May 17, 2014 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
    Commented May 17, 2014 at 8:38

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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