From: Chris Pine <glyconis@...>
Date: 2005-04-30T04:51:29+09:00
Subject: Re: Inverting a regular expression?

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

I seem to remember that if A, B, and C are the sets of languages
accepted by RE's, FA's, and NFA's (not necessarily respectively), that
the easiest way to prove this was to show A as a subset of B, and B of
C, and C of A.  I don't remember which ones are A, B, or C, but I
remember it was a cute proof that way.

:)

But the RE's we use in programming languages are different from what
we use in CS, or at least in *how* we use them.  Surely if I was
trying to match substrings which are not 'Chris' in some large string,
I would find many, many matches.

I guess I'm saying it should always be possible, but maybe not so
useful.  What's the situation where you want to do this?

Chris