From: Nikolai Weibull <mailing-lists.ruby-talk@...>
Date: 2005-05-03T16:27:00+09:00
Subject: Re: Inverting a regular expression?

Dan Doel, May 3:

> Consider the Ruby regex:
> 
>   /(a*)(b*)(\1)(\2)/
> 
> This matches the language { (a^n)(b^m)(a^n)(b^m) }, which I believe
> isn't even context-free …

Backreferencing is an NP-complete problem,
        nikolai

-- 
Nikolai Weibull: now available free of charge at http://bitwi.se/!
Born in Chicago, IL USA; currently residing in Gothenburg, Sweden.
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}