The exponential blowup only occurs in the worst case. I don't have a proof at hand but I suspect that the final automaton shouldn't grow very large if your rege

The exponential blowup only occurs in the worst case. I don't have a proof at hand but I suspect that the final automaton shouldn't grow very large if your regexes are modeling web routes, since they are structured as a tree of paths with lots of "prefix-sharing" and no loops. Other than that, if you are concerned about automaton size you can use a non-deterministc automaton instead of a deterministic one. You spend a bit more time (at each iteration you have to update a list of "active" states, while in the DFA case there is always a single active state) but on the other hand the automaton itself is much more compact.