From: Dan Doel <dolio@...>
Date: 2005-05-03T09:59:47+09:00
Subject: Re: Inverting a regular expression?

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.