From: Logan Capaldo <logancapaldo@...>
Date: 2005-05-03T10:42:50+09:00
Subject: Re: Inverting a regular expression?

On 5/2/05, Dan Doel <dolio@case.edu> wrote:
> Well, if you want an academic answer... :)
> 
> Get a book on automata/computability theory (back when I took such a course,
> we used Automata and Computability by Dexter Kozen; it's pretty good).
> Therein, you'll find algorithms for converting between DFA (discrete finite
> automata) and regular expressions. 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
> 
> Viola.
> 
> However, it should be noted that regular expressions aren't really regular
> these days. For example, Ruby allows the following regex:
> 
>   /(a*)b(\1)/
> 
> Which accepts the language { (a^n)b(a^n) }, which is context free, not
> regular (that is, it cannot be encoded as the language of a finite
> automaton---it requires something like a pushdown automaton (FA with a
> stack)---or the language of a true regular expression---it requires a
> context free grammar). So, if you want to invert an arbitrary
> Ruby/Perl/Python "regular expression," you've got a tougher time on your
> hands.
> 
> -- Dan Doel
> 
> Harry Ohlsen wrote:
> > It was pretty much an academic question, but my colleague actually
> > wanted to do it, so it was of some real-world interest.
> 
> 

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?