.{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.
Is it possible to repeat a wildcard in regex?
regular expressions
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.