3 ms·

That's only true in a naive implementation. In fact, in a naive implementation, it's probably worse than that because there can be loops among epsilon transitio

That's only true in a naive implementation. In fact, in a naive implementation, it's probably worse than that because there can be loops among epsilon transitions. Consider, for example, `(a{star}){star}`. (HN markup prevents use of a kleene star usefully. Sorry.) In a "real" implementation, when computing the next set of states to visit for some position in the input, you explicitly avoid re-visiting states you've already seen for that position in the input. Cox talks about this quite a bit in his articles. The guarantee of the NFA algorithm as presented by Cox is that each NFA state is visited at most once for each position in the input.

amalcon 11y ago
I think wolfgke's point (different from mine, by the way) was that you need to consider each state in each transition list just to check if it's in the set you've already seen. If you're in all states, and all of them transition to all states on an input, that's quadratic: you need to loop through n lists of n states just to check if you've already visited any of them. Of course, I don't think there's an actual regular expression that would produce that automaton using Thompson's algorithm.
- burntsushi 11y ago
  No, it can't happen at all. After processing the first state that visits all states on input i, all subsequent states explored in input i stop before traversing states that have already been visited. Since all states have already been visited, each state after the first on input i can be dismissed in constant time. Given that one can check whether a state has been visited in constant time, this is still just linear, not quadratic. Let's just look at code already. Here's the loop over states at input i: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L165 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If we match a character at input i, then we follow epsilon transitions: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L237 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If we visit a state that we've already seen, skip it: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L300 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If that first state visits all states, then `nlist` (which is maintained while following all states at any position in the input) will contain all states. In each subsequent iteration (line 165), even if the state wants to visit all states, it will be immediately stopped at the first check in line 300. No additional states for that state are followed.

amalcon 11y ago

I think wolfgke's point (different from mine, by the way) was that you need to consider each state in each transition list just to check if it's in the set you've already seen. If you're in all states, and all of them transition to all states on an input, that's quadratic: you need to loop through n lists of n states just to check if you've already visited any of them. Of course, I don't think there's an actual regular expression that would produce that automaton using Thompson's algorithm.

burntsushi 11y ago
No, it can't happen at all. After processing the first state that visits all states on input i, all subsequent states explored in input i stop before traversing states that have already been visited. Since all states have already been visited, each state after the first on input i can be dismissed in constant time. Given that one can check whether a state has been visited in constant time, this is still just linear, not quadratic. Let's just look at code already. Here's the loop over states at input i: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L165 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If we match a character at input i, then we follow epsilon transitions: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L237 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If we visit a state that we've already seen, skip it: https://github.com/rust-lang-nursery/regex/blob/master/src/nfa.rs#L300 https://github.com/rust-lang-nursery/regex/blob/master/src/n... If that first state visits all states, then `nlist` (which is maintained while following all states at any position in the input) will contain all states. In each subsequent iteration (line 165), even if the state wants to visit all states, it will be immediately stopped at the first check in line 300. No additional states for that state are followed.