Hacker News new | ask | show | jobs
by slondr 2258 days ago
RegExp and DFAs are the same computation class, so it's useful sometimes to model them as each other.
2 comments

No idea why you're being downvoted. Also, classical comp. sci technique of reducing your problem into another that's already been solved (with good enough time/mem bounds).
It’s frequently useful, as many regex engines construct DFAs under the hood :)
Not as frequent as you might expect! Most regex engines in common use don't use an automata based implementation, and instead use backtracking. This lets them implement additional non-regular features such as backreferences and recursion.

Even automata based regex engines don't usually build up a full DFA, since the size of the DFA may be exponential in the size of the regex. Instead, an NFA similation might be used, or a hybrid NFA/DFA that builds the DFA during match time, but typically doesn't build out the full DFA.