3 ms·

> The conversion from DFA to NFA [...] I believe you mean NFA to DFA. > [...] would require O(n^2) in that case I believe you mean O(2^n). https://en.wikiped

> The conversion from DFA to NFA [...] I believe you mean NFA to DFA. > [...] would require O(n^2) in that case I believe you mean O(2^n). https://en.wikipedia.org/wiki/Powerset_construction#Complexity https://en.wikipedia.org/wiki/Powerset_construction#Complexi...

lorenzhs 11y ago
Fun with automata: Constructing the minimal DFA for a given NFA is PSPACE-hard. There are families of NFAs with n states so that the powerset automaton has 2^n states, but the minimal DFA has 1 state. Example: Let Σ={a,b} be the alphabet, Q={q1, ..., qn} be the states. q1 has a self-loop with both a and b and a transition to q2 with a. q2 to q(n-1) have transitions with a and b to the next state (q2 -> q3 etc). qn has no transitions. q1 and qn are the only accepting states. This is basically the "n-th-to-last letter was an a" automaton with the modification that the starting state is accepting.
- zamalek 11y ago
  > Constructing the minimal DFA for a given NFA is PSPACE-hard. This isn't really a problem if you incur that cost only once by having the regex compiled when the script is parsed. However, idiomatic JS usually includes regex literals in the closure where it is used - decreasing performance, code reuse and clarity. Why? Probably for the same reasons that regex is being used in the first place.
  - lorenzhs 11y ago
    Well, PSPACE-hard is pretty damn hard, so this really depends on the size and complexity of your NFA ;) Of course most of the time you don't hit the pathological cases like the one I described above. My comment was not meant to provide a guideline on how to fix this, consider it a fun observation on automata theory.
    - zamalek 11y ago
      Indeed. What I failed to communicate was that there is no reason to incur that cost multiple times per process/application. For some reason idiomatic JS encourages incurring that cost multiple times. Your comment shows that this idiomatic form is even more absurd than I originally thought.
cyphar 11y ago
> > The conversion from DFA to NFA [...] > I believe you mean NFA to DFA. Yes, you're right. Whoops :P. > > [...] would require O(n^2) in that case > I believe you mean O(2^n). Ah yes, I forgot that you could chain epsilon edges. Fair enough.
cyphar 11y ago
Actually, the O(n^2) thing is correct for an NFA simulation that tracks states not paths. While there might be O(2^n) paths, there are n states you can be in at any one point. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

lorenzhs 11y ago

Fun with automata: Constructing the minimal DFA for a given NFA is PSPACE-hard. There are families of NFAs with n states so that the powerset automaton has 2^n states, but the minimal DFA has 1 state. Example: Let Σ={a,b} be the alphabet, Q={q1, ..., qn} be the states. q1 has a self-loop with both a and b and a transition to q2 with a. q2 to q(n-1) have transitions with a and b to the next state (q2 -> q3 etc). qn has no transitions. q1 and qn are the only accepting states. This is basically the "n-th-to-last letter was an a" automaton with the modification that the starting state is accepting.

zamalek 11y ago
> Constructing the minimal DFA for a given NFA is PSPACE-hard. This isn't really a problem if you incur that cost only once by having the regex compiled when the script is parsed. However, idiomatic JS usually includes regex literals in the closure where it is used - decreasing performance, code reuse and clarity. Why? Probably for the same reasons that regex is being used in the first place.
- lorenzhs 11y ago
  Well, PSPACE-hard is pretty damn hard, so this really depends on the size and complexity of your NFA ;) Of course most of the time you don't hit the pathological cases like the one I described above. My comment was not meant to provide a guideline on how to fix this, consider it a fun observation on automata theory.
  - zamalek 11y ago
    Indeed. What I failed to communicate was that there is no reason to incur that cost multiple times per process/application. For some reason idiomatic JS encourages incurring that cost multiple times. Your comment shows that this idiomatic form is even more absurd than I originally thought.

cyphar 11y ago

> > The conversion from DFA to NFA [...] > I believe you mean NFA to DFA. Yes, you're right. Whoops :P. > > [...] would require O(n^2) in that case > I believe you mean O(2^n). Ah yes, I forgot that you could chain epsilon edges. Fair enough.

cyphar 11y ago

Actually, the O(n^2) thing is correct for an NFA simulation that tracks states not paths. While there might be O(2^n) paths, there are n states you can be in at any one point. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html