3 ms·
A program that is not exponential in time can't require exponential space, because it can't touch that much space in that little time. Even if you count the NF
by yorwba 7y ago
A program that is not exponential in time can't require exponential space, because it can't touch that much space in that little time.
Even if you count the NFA as part of the input, the expansion into a DFA only happens while matching one character at a time, so to blow up the cache to a size exponential in the number of NFA states, you'd have to be matching on a string of comparable length that forces all possible state combinations to occur.
If you don't count the NFA as part of the input, the matching algorithm for any particular NFA is actually constant-space, because the maximum space required is independent of the string you're processing.
- tempguy9999 7y agoI'm assuming the DFA is built ahead of time, which is pretty conventional in my understanding. This may be something in the article I missed, that the DFA is built incrementally at runtime by this algo. If so, my mistake. I'll read again. @chubot: ok, I am wrong, thanks for the details! Upvoted both.