3 ms·
All regular expressions are deterministic final automata https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministi
by pjc50 5mo ago
All regular expressions are deterministic final automata https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton (finally, a use for my CS course); the extent to which that counts as a virtual machine varies. Some of the regex syntaxes extend it in ways which don't fit in a DFA and do count as a VM; Perl-compatible RE used to be popular (e.g. in Exim).
- anthk 5mo agoInded: https://wiki.xxiivv.com/site/rewriting.html https://wiki.xxiivv.com/site/rewriting.html
- titzer 5mo agoIt's easier to construct NFAs directly from regular expression definitions (rather than DFAs) because implementing the choice operator is easier. We can convert from NFA to DFA with worst-case exponential blowup.