On 04/24/2013 12:45 PM, Tim Shen wrote:
I'm very interested in implementing a NFA->DFA module(does that mean a Thompson automaton?) so that the exponential searching algorithm can be reduced to a linear state transition(though the states may be potentially exponential) loop. I can't understand how some language dare use a search algo as a final solution :)
DFA construction requires exponential space even for a fairly restricted subset of regular expressions. The cache misses from large DFAs (which can arise in practice, not just with maliciously crafted regular expressions) often negate the wins from a simplified execution model.
-- Florian Weimer / Red Hat Product Security Team
