# Class of languages accepted by Python RegEx?

Python / Java / Perl / Ruby / etc. extend regular expressions to permit look-ahead and look-behind, e.g., LookAround:

(?=...)
(?<=...)
(?!...)
(?<!...)


I would appreciate a formal definition of the languages accepted by these modern "regex" modules. They don't reach context-free, do they? What is the superset of regular languages achieved by these recursive-backtracking additions to regular languages?

Lookaround in regular expressions does not allow them to recognize non-regular languages. This is difficult to see in the standard automata formalism, but this paper describes using Brzozowski's more intuitive "derivative" formalism, which allows defining "extended regular expressions" affording complementation $\neg r$ and intersection $r \& s$. The set of regular languages is also closed under these operations, and looaround operations can be defined in terms of them. For example, negative lookahead $r(?!s)p$ can be written as $r(p\&\neg (s.*))$
This post describes the power of "perl compatible regular expressions" (PCREs). They can recognize at least the context free languages and more. However, Python does not use full PCREs, and in particular lacks the DEFINE keyword, which the author used to prove it can recognize all context-free languages. (The proof is basically embedding BNF-style grammar productions into a PCRE.)
I'm not aware of a way of embedding BNF-style productions into python regular expressions, so it's unclear whether python regexes can recognize all CFLs. They can also clearly recognize non-regular languages like the collection of strings on the alphabet $\{a\}$ which have a composite length r'^(aa+)(\1)+\$', which is not even context-free.