3 ms·

To sum it up: The NFA and the DFA have exactly the same Big O complexity. The NFA is just slower by some factor. So that's not much of a difference. The real

To sum it up: The NFA and the DFA have exactly the same Big O complexity. The NFA is just slower by some factor. So that's not much of a difference. The real difference is between dynamic programming and backtracking. When you implement an NFA with dynamic programming, you're still O(N) with respect to the input no matter what. But when you use backtracking, as Perl does, you're prone to combinatorial explosions in some cases. Also keep in mind that PCRE are not regular expressions. They're more expressive than that, and can express more than just regular grammars. That's possible because when you start with backtracking, it is relatively easy to add other niceties on top of pure regular expressions.

brudgers 11y ago
Though there is an equivalent DFA for every NFA, the DFA can have an exponentially larger number of states than the NFA, though my understanding is that's not usually the case in practice. In any event the processing time of an NFA implementation can reflect this explosion since the actual implementation algorithm of a finite state machine on ordinary hardware has to be deterministic.
- loup-vaillant 11y ago
  > the DFA can have an exponentially larger number of states than the NFA Yep. Which is why some implementation fall back to NFA when the number of state of the DFA reaches some predefined threshold. > In any event the processing time of an NFA implementation* can reflect this explosion* Well, not necessarily. Trial and error (backtracking) is not the only way to simulate an NFA. A more reliable way to do it is to execute the multiple choices in parallel. This nullifies the combinatorial explosion because the different threads share a great deal of information. A thread of execution in a finite automaton has exactly 2 pieces of information: the current position in the character stream, and the current state. In the case of a DFA, you stick to a single thread of execution, and if you fail, there's nothing to backtrack to anyway. In the case of an NFA, you can maintain a set of current states. And that set will never be bigger than the number of states in your NFA. The algorithm looks like this: Set = [Start_state] Until input is empty: Read the next character New_set = [] // empty set For each state in your old set: Add all the possible next states to New_set Set = New_set If New_set is empty You failed to recognised the input You successfully recognised the input
  - brudgers 11y ago
    Parallel processing won't convert an exponential process into a polynomial one...unless one can run an exponential number of processes simultaneously.
    - loup-vaillant 11y ago
      Not in the general case. But in this case, yes it can. First, I suggest you read the fucking link I summarised in the first place: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html Second, this fucking course is really good: https://www.coursera.org/course/automata https://www.coursera.org/course/automata (I have taken it myself.) If you have a dozen hours to spare, it is highly recommended. Third, you may want to take a look at this… fucking… analogy: 0 / \ | | \ / 1 / \ | | \ / 2 . . . N-2 / \ | | \ / N-1 / \ | | \ / N The number of paths from top to bottom is 2^N. If you want to try them all, that will indeed take exponential time, parallelism or not. But when you process an NFA, you don't care which path you have taken. So you can forget about which path you have "actually" taken. The thing is, when you branch from K, both branches land at the same spot: K+1. So you merge those branches. Then you split again. So when you're going through this graph, the maximum number of actual threads you will ever run in parallel is 2. That's nowhere near the expected 2^N. Here lies the beauty of proper NFA processing. By merging the parallel threads at each opportunity, you keep their numbers down to the number of states in the NFA —at most. As a result, the worst running time of a good NFA algorithm is O(N*S), where N is the length of the input, and S the number of states in the NFA. And the worst running space is O(S). Of course, if you're fail to merge the threads (like backtracking), then your worst case goes back to exponential. On the other hand, it can give you extra powers such as back references.
      - brudgers 11y ago
        Real world regular expressions Regular expression usage in real programs is somewhat more complicated than what the regular expression implementations described above can handle... I'm unable to see how the approach suggested in the paper could be made idempotent with Perl's regular expression engine while still maintaining linear performance. Though admittedly idempotence is a strong form of "Perl Compatible". But as I'm not particularly bright, there's no need to try and explain.

brudgers 11y ago

Though there is an equivalent DFA for every NFA, the DFA can have an exponentially larger number of states than the NFA, though my understanding is that's not usually the case in practice. In any event the processing time of an NFA implementation can reflect this explosion since the actual implementation algorithm of a finite state machine on ordinary hardware has to be deterministic.

loup-vaillant 11y ago
> the DFA can have an exponentially larger number of states than the NFA Yep. Which is why some implementation fall back to NFA when the number of state of the DFA reaches some predefined threshold. > In any event the processing time of an NFA implementation* can reflect this explosion* Well, not necessarily. Trial and error (backtracking) is not the only way to simulate an NFA. A more reliable way to do it is to execute the multiple choices in parallel. This nullifies the combinatorial explosion because the different threads share a great deal of information. A thread of execution in a finite automaton has exactly 2 pieces of information: the current position in the character stream, and the current state. In the case of a DFA, you stick to a single thread of execution, and if you fail, there's nothing to backtrack to anyway. In the case of an NFA, you can maintain a set of current states. And that set will never be bigger than the number of states in your NFA. The algorithm looks like this: Set = [Start_state] Until input is empty: Read the next character New_set = [] // empty set For each state in your old set: Add all the possible next states to New_set Set = New_set If New_set is empty You failed to recognised the input You successfully recognised the input
- brudgers 11y ago
  Parallel processing won't convert an exponential process into a polynomial one...unless one can run an exponential number of processes simultaneously.
  - loup-vaillant 11y ago
    Not in the general case. But in this case, yes it can. First, I suggest you read the fucking link I summarised in the first place: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html Second, this fucking course is really good: https://www.coursera.org/course/automata https://www.coursera.org/course/automata (I have taken it myself.) If you have a dozen hours to spare, it is highly recommended. Third, you may want to take a look at this… fucking… analogy: 0 / \ | | \ / 1 / \ | | \ / 2 . . . N-2 / \ | | \ / N-1 / \ | | \ / N The number of paths from top to bottom is 2^N. If you want to try them all, that will indeed take exponential time, parallelism or not. But when you process an NFA, you don't care which path you have taken. So you can forget about which path you have "actually" taken. The thing is, when you branch from K, both branches land at the same spot: K+1. So you merge those branches. Then you split again. So when you're going through this graph, the maximum number of actual threads you will ever run in parallel is 2. That's nowhere near the expected 2^N. Here lies the beauty of proper NFA processing. By merging the parallel threads at each opportunity, you keep their numbers down to the number of states in the NFA —at most. As a result, the worst running time of a good NFA algorithm is O(N*S), where N is the length of the input, and S the number of states in the NFA. And the worst running space is O(S). Of course, if you're fail to merge the threads (like backtracking), then your worst case goes back to exponential. On the other hand, it can give you extra powers such as back references.
    - brudgers 11y ago
      Real world regular expressions Regular expression usage in real programs is somewhat more complicated than what the regular expression implementations described above can handle... I'm unable to see how the approach suggested in the paper could be made idempotent with Perl's regular expression engine while still maintaining linear performance. Though admittedly idempotence is a strong form of "Perl Compatible". But as I'm not particularly bright, there's no need to try and explain.