regular expression for nested matching braces

[Tim Peters]

[Piet van Oostrum]
> ...
> In fact python's regular expressions are a little bit stronger than
> the theoretical ones because of the allowed \n constructs, but still
> can't count.

If you're into this kind of thing, doing a google search on

    "regular expression" "NP complete"

turns up several linear-time reductions transforming NP-complete problems
into matching-with-backreferences problems.  IOW, adding backreferences to
theoretical regexps turns the regexp matching problem from polynomial time
into "almost certainly" exponential time.  In that sense, backreferences add
enormous power.  But counting is *really* hard <wink>.