2 ms·
Regular expressions are not Turing-complete.
by Patryk27 5mo ago
Regular expressions are not Turing-complete.
- 0xffany 5mo agoTrue in the CS Theory space, but most modern regex engines implement a few niceties which make their "regex" turing complete. https://blog.poisson.chat/posts/2024-06-18-turing-regex.html https://blog.poisson.chat/posts/2024-06-18-turing-regex.html
- benchloftbrunch 5mo agoJavascript/PCRE/etc regexes have additional features (like backreferences) that give them strictly more computational power than a regular DFA/NFA. (Still not Turing complete though without external control flow to support arbitrary iteration/recursion, like is done here)