Hacker News new | ask | show | jobs
by saagarjha 2258 days ago
It’s frequently useful, as many regex engines construct DFAs under the hood :)
1 comments

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.