From: Nikolai Weibull <mailing-lists.ruby-talk@...>
Date: 2005-04-30T06:26:03+09:00
Subject: Re: Inverting a regular expression?

Chris Pine, April 30:

> > The issue of matching an inverted regular expression also depends on
> > what kind of finite state automaton is used.  It's simple to do for
> > deterministic finite automatons; not so simple for nondeterministic ones
> > (actually, I'm not even sure if it's possible at all).
> 
> Hmm...  I'm not sure this is true.  As I recall, a language accepted
> by a regular expression can always be described as the language
> accepted by some FA, or by some non-deterministic FA; in other words,
> that they are all equivalent.

Sure, they're equivalent.  That parentheses was false, sorry.  However,
it's a lot easier to do for deterministic FAs than for nondeterministic
FAs, as far as I know,
        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);}