what 262,715 regex questions on stack overflow haven’t answered

I too have wondered why regex engines don’t support intersection and such. I’d like to know what implementation approach they’re using, and what implications it has for complement, intersection etc. I recall complement being really inefficient to implement, like making the DFA exponentially larger, something like that.

My understanding, mostly from Wikipedia, is that if r is the regex size and n is the input size, then:

• An NFA runs in O(rn) time.
• If you convert the NFA to a DFA, its size is O(2^r)! But then it runs in O(n).
• There’s also “lazy DFA” that I don’t really know the properties of.

Is the idea to use an NFA and eat the worst-case extra factor of r running time, using optimizations to try to reduce that factor in practice? Does this make intersection easy to implement efficiently?