Harry Ohlsen, May 4:

> > From: Dan Doel [mailto:dolio / case.edu] 

> > 1) Convert the regex to a DFA
> > 2) Invert the accept states of the DFA, causing it to accept the
> >    complement of the initial language
> > 3) Convert the modified DFA into a regex

> Good point!  I assume steps 1 and 2 are left as exercises for the reader
> :-).

Actually, it's not a very good point, as it isn't quite right.  See my
response to this thread for the corrected method of conversion.

> > However, it should be noted that regular expressions aren't really
> > regular these days. For example, Ruby allows the following regex:

> >   /(a*)b(\1)/

> > Which accepts the language { (a^n)b(a^n) }, which is context free,
> > not regular (that is, it cannot be encoded as the language of a
> > finite automaton---it requires something like a pushdown automaton
> > (FA with a stack)---or the language of a true regular
> > expression---it requires a context free grammar). So, if you want to
> > invert an arbitrary Ruby/Perl/Python "regular expression," you've
> > got a tougher time on your hands.

> Another good point.  Yes, REs as used in computer languages have
> certainly moved on.

Well, some would say that it's evolution, while others would call it an
utter disregard of the rules.  Again, backreferencing is an NP-complete
problem, which, as you know, has some dire implications,
        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);}