Kristof Bastiaensen, May 3:

> On Mon, 02 May 2005 20:55:35 -0400, Dan Doel wrote:

> > 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

> I am afraid that wouldn't work.  For example /ab/ would become
> /[^a][^b]/, which isn't the complement of /ab/.

Yes, Dan's description isn't quite clear enough.  Here's what you do to
invert a DFA:

1.  If the DFA isn't complete, i.e., it doesn't have transitions leaving
    each state for each input symbol, add a new non-accepting state, call
    it sink, and add transitions to it for each such input symbol.

2.  Make any accepting state non-accepting and any non-accepting state
    accepting.

Very straightforward.  This, however, only works for DFAs, not NFAs.  A
method to take the complement of an NFA would include a step 0 that
would convert the NFA to a DFA.  This solution isn't great, though, as
you will have to do the conversion from NFA to DFA, which we often don't
want to do.

Enjoy,
        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);}