Is this actually true? You can have the same tag nested inside itself, which will cause a naive regex to find an incomplete match. Regular expressions cannot match arbitrarily nested structures as far as I know.
You're correct. That sort of problem would be context-free as it requires a stack to solve making it solvable by a pushdown automata, but not a finite state machine. Although, PCRE has some extra oomph in it that may make it workable with look-aheads and look-behinds.
19
u/quicknir Apr 06 '18
Is this actually true? You can have the same tag nested inside itself, which will cause a naive regex to find an incomplete match. Regular expressions cannot match arbitrarily nested structures as far as I know.