[bigdict]

But... they are equivalent?

[Kaliboy]

Yeah 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.

[xpon]

Modulo an exponential blowup! That’s like saying P is equivalent to NP.

[tgv]

Depends 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]

Running NFA is O(nm) not NP.

[tgv]

Sorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.

[benchloftbrunch]

So it is NP (in fact P)

[froh]

The 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]

No, 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

[IsTom]

And there are language families where minimal DFA is still exponentially large compared to NFA.