6 ms·
Modulo an exponential blowup! That’s like saying P is equivalent to NP.
by xpon 4mo ago
Modulo an exponential blowup! That’s like saying P is equivalent to NP.
- froh 4mo agoThe blow up is exponential for carefully crafted academical regular expressions. im practice is a good idea to build a DFA from your regex, up front (re2) or lazily (ripgrep)
- pkal 4mo agoNo, because you can compute the optimal automaton (as in least number of states) that recognizes the same language: https://en.wikipedia.org/wiki/DFA_minimization https://en.wikipedia.org/wiki/DFA_minimization
- IsTom 4mo agoAnd there are language families where minimal DFA is still exponentially large compared to NFA.
- tgv 4mo agoDepends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.
- DmitryOlshansky 4mo agoRunning NFA is O(nm) not NP.
- tgv 4mo agoSorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.
- benchloftbrunch 4mo agoSo it is NP (in fact P)