3 ms·
RegExp and DFAs are the same computation class, so it's useful sometimes to model them as each other.
by slondr 7y ago
RegExp and DFAs are the same computation class, so it's useful sometimes to model them as each other.
- Pmop 7y agoNo 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).
- saagarjha 7y agoIt’s frequently useful, as many regex engines construct DFAs under the hood :)
- burntsushi 7y agoNot 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.