3 ms·

What are you talking about? "Not a language?" "DFA is the absurdity?" I'm sorry, I don't follow.

rurban 5y ago
read for example about the state explosion of DFA's: "It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation. For example, it is much easier to prove closure properties of regular languages using NFAs than DFAs." https://en.m.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.m.wikipedia.org/wiki/Nondeterministic_finite_auto... but more importantly look at the various attempts to the solve backtracking "problem" (stack overflow by unbounded recursion), as done recently in perl and pcre, which led to more insecure AND more unmaintainable regex code by converting their simple recursion to iterations on the heap. first it got much slower, as the state is now handled on the heap, and second it got much more insecure as DOS attacks can now exhaust the whole heap, not just around 1024 stack depths. and third, it got 10x more complicated, and unreadable. ad language: you can of course define a language by forbidding left recursion, which yacc folks would prefer. but you can define it much easier with left recursive parsers, like 10x smaller. of course you can always expand simple NFA's to deterministic DFA's at the cost of exponential state explosion and increased complexity. but it is a monstrosity only impractical CS folks prefer. SW engineers prefer the similar, faster and more secure NFA backtracking versions, as long as you count the stack depth.
- colanderman 5y ago
  As I mentioned elsewhere, linear performance is a hard requirement for some domains such as intrusion prevention. Unbounded recursion isn't the primary problem; exponential runtime is. If state-space explosion is a concern, you can implement a non-backtracking regular expression matcher using term rewriting. For true regular expressions, the size of the rewritten terms are a function of the size of the pattern (and thus performance is linear). For non-regular expressions, this does not hold.
  - jonstewart 5y ago
    You can also just implement an NFA but apply determinization to much of it, with tight memory allocation bounds, to get most of the benefit.
    - rurban 5y ago
      yeah, with practical backtracking regexes they limit their recursion depth to about 10. with DFA expansion this was pretty hard to implement, with simple NFA's it was trivial. Pratt and esp. PEG solve the determinism problem, even better than yacc.

read for example about the state explosion of DFA's: "It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation. For example, it is much easier to prove closure properties of regular languages using NFAs than DFAs." https://en.m.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.m.wikipedia.org/wiki/Nondeterministic_finite_auto... but more importantly look at the various attempts to the solve backtracking "problem" (stack overflow by unbounded recursion), as done recently in perl and pcre, which led to more insecure AND more unmaintainable regex code by converting their simple recursion to iterations on the heap. first it got much slower, as the state is now handled on the heap, and second it got much more insecure as DOS attacks can now exhaust the whole heap, not just around 1024 stack depths. and third, it got 10x more complicated, and unreadable. ad language: you can of course define a language by forbidding left recursion, which yacc folks would prefer. but you can define it much easier with left recursive parsers, like 10x smaller. of course you can always expand simple NFA's to deterministic DFA's at the cost of exponential state explosion and increased complexity. but it is a monstrosity only impractical CS folks prefer. SW engineers prefer the similar, faster and more secure NFA backtracking versions, as long as you count the stack depth.

colanderman 5y ago
As I mentioned elsewhere, linear performance is a hard requirement for some domains such as intrusion prevention. Unbounded recursion isn't the primary problem; exponential runtime is. If state-space explosion is a concern, you can implement a non-backtracking regular expression matcher using term rewriting. For true regular expressions, the size of the rewritten terms are a function of the size of the pattern (and thus performance is linear). For non-regular expressions, this does not hold.
- jonstewart 5y ago
  You can also just implement an NFA but apply determinization to much of it, with tight memory allocation bounds, to get most of the benefit.
  - rurban 5y ago
    yeah, with practical backtracking regexes they limit their recursion depth to about 10. with DFA expansion this was pretty hard to implement, with simple NFA's it was trivial. Pratt and esp. PEG solve the determinism problem, even better than yacc.