# Is it possible to repeat a wildcard in regex?

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

• 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 – ratchet freak May 17 '14 at 2:31
• @ratchetfreak I suspected that was the case (see my note*). How can you prove that that is the case? – VF1 May 17 '14 at 3:01
• 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. – Blrfl May 17 '14 at 3:26
• \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. – 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.