1
$\begingroup$

I recently learned that regex support backreference which enables referring to a matched group in the pattern itself. E.g. a regex (.)\1{2,} matches two or more consecutive appearances of the same character like 'aa', '...', '------', etc. However, such feature seems exceeds the capability of finite state machine which is the underlying implementation of regex. It seem like it needs to remember the matched part and match with it again, but the matched part its self have infinite possible values. I'm just speculating but have no idea to prove or disprove it. My doubt is, does the regex with backreference still have finite number of states?

$\endgroup$
2
$\begingroup$

No, it doesn't. With backreferences, it is trivial to write a regex that matches exactly the standard textbook example of a non-regular language, $\{ a^nb^n \mid n \in \mathbb{N} \}$. A finite number of states can only distinguish between finitely many different prefixes in $a^*$, so it won't do.

$\endgroup$
2
  • $\begingroup$ Thank you! Concise and easy-understanding explanation. Just a follow-up question: since it's infinite, so how would the regex with backreference be implemented? Push-down automata or something? $\endgroup$
    – seven7e
    Jun 17 '20 at 7:19
  • 1
    $\begingroup$ Yes, essentially, although it's much more complicated due to all the features. You can check out implementations for yourself, e.g. at vcs.pcre.org/pcre2/code/trunk/src/… (which appears to use some sort of stack but also appears to impose a maximum depth) or github.com/Perl/perl5/blob/blead/regexec.c (which I find pretty unreadable, but there is a high-level explanation of how it works). $\endgroup$ Jun 17 '20 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.