11 ms·
This is amazing. I'm at loss for words. During my CS years I remember being fascinated by NFA's, as opposed to boring single universe DFA's. For some reason I
by Kaliboy 5mo ago
This is amazing. I'm at loss for words.
During my CS years I remember being fascinated by NFA's, as opposed to boring single universe DFA's.
For some reason I internalized that I would never see something like an NFA implemented beyond text books.
Then came Carlini.
- bigdict 5mo agoBut... they are equivalent?
- xpon 5mo agoModulo an exponential blowup! That’s like saying P is equivalent to NP.
- froh 5mo 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 5mo 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 5mo agoAnd there are language families where minimal DFA is still exponentially large compared to NFA.
- tgv 5mo 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 5mo agoRunning NFA is O(nm) not NP.
- benchloftbrunch 5mo agoSo it is NP (in fact P)
- tgv 5mo agoSorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.
- Kaliboy 5mo agoYeah I know, but I thought I was doing purely theoretical excercises. And we always changed the regex NFA to an equivalent DFA and that was the implementation. So somehow I managed to internalize the idea that an NFA is purely theoretical and can't be built.