search (match) backward

[Tim Peters]

[Greg Ewing]
> ...
> This raises the interesting question of whether there is an
> algorithm for reversing an RE (i.e. find an RE which matches
> the reverse of the strings that the original RE matches).
> Can it even be done in general? My intuition says yes, but
> I can't think of a proof off the top of my head.

Yes, but thinking about it in terms of REs is exceedingly clumsy.  The proof
is easy if you look at machines instead:  build a state machine that accepts
the language defined by the RE.  Build a derived machine with the same set
of states, but invert the transitions, make the new machine's accepting
states the original machine's start states, and make the new machine's start
states the original machine's accepting states (special case here:  if the
language is empty, there may not be any accepting states in the original
machine).  You're done!  By construction, you now have an NFA that accepts
the reversed language (we're really just running the original machine
"backwards").

Convert to a DFA, then back to an RE.  This is how it's done in practice,
too -- trying to approach it at the level of syntactic transformation is a
god-awful mess.  As Jon Fernquest got close <wink> to claiming a short while
ago, REs are a miserable notation for some elegant machinery.

irregularly y'rs  - tim