From: Kristof Bastiaensen <kristof@...>
Date: 2005-05-03T18:24:31+09:00
Subject: Re: Inverting a regular expression?

On Mon, 02 May 2005 20:55:35 -0400, Dan Doel wrote:
> Well, if you want an academic answer... :)
> 
> Get a book on automata/computability theory (back when I took such a course,
> we used Automata and Computability by Dexter Kozen; it's pretty good).
> Therein, you'll find algorithms for converting between DFA (discrete finite
> automata) and regular expressions. You can invert a regular expression as
> follows:
> 
> 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
> 
> Viola.
> 

I am afraid that wouldn't work.  For example /ab/ would become
/[^a][^b]/, which isn't the complement of /ab/.  Now the string
"ac" would match neither.  (Nor any string with more than two
characters).

KB