4 ms·
IIRC, regex can be implemented by an NFA which can't solve balanced parentheses that are part of regex syntax.
by ac42 7y ago
IIRC, regex can be implemented by an NFA which can't solve balanced parentheses that are part of regex syntax.
- ac42 7y agohttps://en.m.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.m.wikipedia.org/wiki/Nondeterministic_finite_auto...
- mikejb 7y agoCorrect, though there are multiple interpretations of what a "regex" is. In the theoretical sense you're correct, though some (most programmers, I'd say) mean "PCRE" when they say regex. And PCREs are pretty powerful, see [1] for example [1] https://news.ycombinator.com/item?id=9748736 https://news.ycombinator.com/item?id=9748736
- nabla9 7y agoRegex has two different meaning depending on the context. One is CS definition of regular expression matcher for regular languages. The other is extension of that into non-regular languages, typically PCRE compatible.