ietf-mta-filters
[Top] [All Lists]

Re: Complexity of :matches ?

2005-07-12 05:13:50

In particular, counted repetitions ({n,m}) have to be expanded when
figuring the 'N' of the size of the regexp, while back-references
(\digit) are, IIRC, worst-case exponential to match.

That's because back-references leave the class of regular languages,
but I am surprised right now that the manual does not say so.

This egrep expression shows that is an entertaining way:

^(aa+)\1+$

It does not match if the length of the string of a characters is prime,
because the group is a prime factor.  A DFA can not do that, because it
contains only a finite number of states, thus being unable to compute
with natural numbers.  I guess I should think less about regular
expressions. :)

Michael


<Prev in Thread] Current Thread [Next in Thread>