3 ms·
Conversion of an NFA graph to DFA (in regex processing) seems to be a kind of supercompilation. The NFA is treated as a process, and is simulated for all possib
by kazinator 3y ago
Conversion of an NFA graph to DFA (in regex processing) seems to be a kind of supercompilation. The NFA is treated as a process, and is simulated for all possible input symbols at every step. The supercompiler makes note of what states it goes into and turns sets of them into DFA states.
- gbacon 3y agoWithout backreferences, it has a worst-case exponential blow up due to the DFA possibly needing to simulate that many simultaneous NFA states. Regex matching with backreferences is NP-hard. - https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html - https://perl.plover.com/NPC/NPC-3COL.html https://perl.plover.com/NPC/NPC-3COL.html