4 ms·

Backtracking is required in a lot of cases. Consider matching the pattern /^(AA|AB)*$/ against the string "AAAAAAAAB". Before it can come up with the answer (it

Backtracking is required in a lot of cases. Consider matching the pattern /^(AA|AB)*$/ against the string "AAAAAAAAB". Before it can come up with the answer (it doesn't match) the engine has to backtrack all the way from right to left.

edwintorok 11y ago
that can be compiled to a state machine where a decision to switch states is taken based on current character only, and when all input is consumed you are either in an accepting or rejecting state. In your case I think it only needs 2 states: state 0 moves to state 1 when it sees an A, and state 1 moves to state 0 when it sees either A or B. For your string it'll be in state 0 when it sees a B and thus rejects it.
- thaumasiotes 11y ago
  ┌┐ ↓│ ┌────┴┐ ┌─→│ │←──┐ │ └─────┘ │ ╔════╧═╗ ┌──┴──┐ ├─→║ ╟───A──→│ │ ╚══════╝ └─┬───┘ ↑ │ └─────A,B────┘ Three states if you want to process the whole input. If your model is "reject when you fail to find an appropriate transition" rather than "reject if, after processing the string, you're in a reject state", then you don't need the failure trap and you can do it in two states. Backtracking is definitely not required, nor helpful.
  - hobs 11y ago
    That diagram is quite pretty, did you just hand code it?
    - thaumasiotes 11y ago
      Yeah, all manual. :/ http://unicode-table.com/en/blocks/box-drawing/ http://unicode-table.com/en/blocks/box-drawing/ http://unicode-table.com/en/sets/arrows-symbols/ http://unicode-table.com/en/sets/arrows-symbols/
dpkendal 11y ago
Not true. Finite automata (NFAs, DFAs) can match that pattern (and any pattern that doesn't involve backreferences or lookaround) in O(n) time where n is the size of the input string. DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression, but this is far better in most cases than the exponential worst-case time in terms of the input string offered by backtracking implementations. See https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ for information on finite-state-machine implementations of regexp matching.
- thaumasiotes 11y ago
  > DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression What? Why is that? If the NFA has n states, then the DFA in principle might need one state for every possible set of states the NFA might be in, of which there are 2^n. Where does n^2 come from?
  - dpkendal 11y ago
    My mistake, I meant O(2 ^ n) indeed. Regardless, having exponential time complexity in terms of the regular expression (which is usually controlled by the programmer) where the processing is done at compile-time is much better than having exponential complexity in terms of the input string (which often comes from an untrusted source) where the processing is done at run-time.

edwintorok 11y ago

that can be compiled to a state machine where a decision to switch states is taken based on current character only, and when all input is consumed you are either in an accepting or rejecting state. In your case I think it only needs 2 states: state 0 moves to state 1 when it sees an A, and state 1 moves to state 0 when it sees either A or B. For your string it'll be in state 0 when it sees a B and thus rejects it.

thaumasiotes 11y ago
┌┐ ↓│ ┌────┴┐ ┌─→│ │←──┐ │ └─────┘ │ ╔════╧═╗ ┌──┴──┐ ├─→║ ╟───A──→│ │ ╚══════╝ └─┬───┘ ↑ │ └─────A,B────┘ Three states if you want to process the whole input. If your model is "reject when you fail to find an appropriate transition" rather than "reject if, after processing the string, you're in a reject state", then you don't need the failure trap and you can do it in two states. Backtracking is definitely not required, nor helpful.
- hobs 11y ago
  That diagram is quite pretty, did you just hand code it?
  - thaumasiotes 11y ago
    Yeah, all manual. :/ http://unicode-table.com/en/blocks/box-drawing/ http://unicode-table.com/en/blocks/box-drawing/ http://unicode-table.com/en/sets/arrows-symbols/ http://unicode-table.com/en/sets/arrows-symbols/

dpkendal 11y ago

Not true. Finite automata (NFAs, DFAs) can match that pattern (and any pattern that doesn't involve backreferences or lookaround) in O(n) time where n is the size of the input string. DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression, but this is far better in most cases than the exponential worst-case time in terms of the input string offered by backtracking implementations. See https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ for information on finite-state-machine implementations of regexp matching.

thaumasiotes 11y ago
> DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression What? Why is that? If the NFA has n states, then the DFA in principle might need one state for every possible set of states the NFA might be in, of which there are 2^n. Where does n^2 come from?
- dpkendal 11y ago
  My mistake, I meant O(2 ^ n) indeed. Regardless, having exponential time complexity in terms of the regular expression (which is usually controlled by the programmer) where the processing is done at compile-time is much better than having exponential complexity in terms of the input string (which often comes from an untrusted source) where the processing is done at run-time.