Chris Pine
4/29/2005 7:51:00 PM
> 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