[Solved]: Is it possible to repeat a wildcard in regex?

Problem Detail: 

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

Asked By : VF1

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25829

3.2K people like this

 Download Related Notes/Documents