6
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

I think the answer is "it's complicated", and they probably do not recognize a definite level in the Chomsky hierarchy

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.

$\endgroup$
  • $\begingroup$ "The set of regular languages is also closed under these operations, and lookaround operations can be defined in terms of them." Excellent point! $\endgroup$ – Joseph O'Rourke Feb 25 '17 at 1:14
  • 1
    $\begingroup$ Shameless plug, but if you're interested in exploring formal languages and python regular expressions, you can check out my work-in-progress library for generating random elements of regular languages. Here's the PR where I introduced most of the functionality based on Brzozowski derivatives, and here's the PR where I implement lookaround support. $\endgroup$ – intractelicious Feb 25 '17 at 1:32

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.