Dan Doel
5/3/2005 3:15:00 AM
I've never investigated things like regex engines in real programming
languages. They probably do convert the regex into some 'nicer' form for
actually computing matches.
If it's simply a DFA, then yeah, you can just invert the accept states. That
might even work in the case of a PDA (not too sure; it's been a while)
(also note, it depends on the type of PDA. They can accept based either on
state or empty stack, although you can convert between them. The latter is
probably harder to invert as-is).
I think the situation is even worse, however. Consider the Ruby regex:
/(a*)(b*)(\1)(\2)/
This matches the language { (a^n)(b^m)(a^n)(b^m) }, which I believe isn't
even context-free (someone should check me on this; I've been fumbling
around reading sites on the pumping lemma, but it's been like a year and a
half since I really knew this stuff). So whatever format they convert the
regex into to actually figure out the match, it probably isn't as simple as
even a PDA (you need at least a linear bounded automaton---Turing machine
with a finite tape---to match a context-sensitive language), and it's
probably not as simple as flipping some bits to match the complement.
In fact, now that I think of it, I'm sure people have developed much better
heuristics for matching these kinds of things than building and simulating
a theoretical machine. So even with the guts of the regex, it's probably
not easy to invert.
In addition, although Ruby regexes can match the language above---which I
think is context-sensitive---that doesn't mean it can match all
context-sensitive languages. For instance, I don't think you can match the
classic context-sensitive language { (a^n)(b^n)(c^n) }, because you can't
access the length of previous groups. In fact, I don't think you can even
match { (a^n)(b^n) }, so Ruby regexes can't even match every context-free
language, just a (small?) subset! So, it's entirely possible that the
complement of a Ruby regex isn't expressible as a Ruby regex at all. Then
again, I'm not going to try to prove either way. :)
Anyhow, this is only an issue if you allow references to previously matched
groups. If you eliminate those, Ruby regexes are actually regular
expressions (with some enhancements to make them more concise), and then
you can invert them using the steps I listed earlier.
Apologies for the lengthy post.
-- Dan Doel
Logan Capaldo wrote:
> In this case, I would imagine that (Not having taken theory of
> computation yet, next semester! woo hoo) Onigurma and the like convert
> the regex into a DFA or a PA anyway at some point. Couldn't you go
> into the guts and invert the DFA as you describe (not necessarialy
> generating the inverted regex) and use the new DFA or PA to match
> against the input?