Brzozowski's algorithm...

reachable: Return only the states and transitions reachable from the start states.
subset: The subset construction to turn an NFA into a DFA.
reverse: Reverse all of the transitions and swap the start and final state sets. (Eg, if the NFA has a transition (1, 'a') -&gt; 4, it would become (4, 'a') -&gt; 1.)

I am in the process of writing a "proof of concept" NFA engine and then applying a home-brewed optimization to it. Here are my claims:

Said optimization can be incrementally applied, as much or little as you want. (There is an exponential possible blow-up in the size of the RE in optimizing it.)
The optimization leaves the RE an NFA. That is it means that you will continue to find the same matches, and it is compatible with all features you can shove into an NFA. (It does not optimize all features, it just is willing to recognize that there are bits it can't optimize, and treat them properly.)
Any RE which could be computed by an NFA can be optimized perfectly - the time to test a string will be linear in the length of the string.
This is true even though you are capturing backreferences.
The bulk of this optimization could be applied lazily at run-time, but my proof of concept won't show that. Said lazy approach is also unavoidably slow.

Expect more from me later. (Like in a month or two.)

Cheers,
Ben

Welcome to IWETHEY!