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

<p>Lookaround in regular expressions does not allow them to recognize non-regular languages. This is difficult to see in the standard automata formalism, but <a href="http://www.ccs.neu.edu/home/turon/re-deriv.pdf" rel="nofollow noreferrer">this paper</a> describes using Brzozowski's more intuitive "derivative" formalism, which allows defining "extended regular expressions" affording complementation $\neg r$ and intersection $r \&amp; 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\&amp;\neg (s.*))$</p>

<p><a href="https://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html" rel="nofollow noreferrer">This post</a> 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 <code>DEFINE</code> 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.) </p>

<p>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 <code>r'^(aa+)(\1)+$'</code>, which is not even context-free.</p>

CC BY-SA 3.0
2017-02-25T01:14:15.370Z
"The set of regular languages is also closed under these operations, and lookaround operations can be defined in terms of them." Excellent point!
Joseph O'Rourke
CC BY-SA 3.0
2017-02-25T01:32:03.997Z
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](https://github.com/lucaswiman/revex/pull/2) where I introduced most of the functionality based on Brzozowski derivatives, and [here's the PR](https://github.com/lucaswiman/revex/pull/12) where I implement lookaround support.
Lucas Wiman
CC BY-SA 3.0
2017-02-25T01:10:06.020Z
2017-02-25T01:10:06.020Z
Lucas Wiman
<p>Python / Java / Perl / Ruby / etc. extend regular expressions to permit
look-ahead and look-behind, e.g.,
<a href="http://www.rexegg.com/regex-lookarounds.html" rel="noreferrer">LookAround</a>:</p>

<pre><code>(?=...)
(?&lt;=...)
(?!...)
(?&lt;!...)
</code></pre>

<p>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?</p>

CC BY-SA 3.0
2017-02-24T23:08:34.030Z
From https://en.wikipedia.org/wiki/RE2_(software) it seems [PCRE](https://en.wikipedia.org/wiki/PCRE) can be exponential time. It also seems that Perl's RE might be Turing complete.
Kaveh
<fl.formal-languages>
Class of languages accepted by Python RegEx?
Joseph O'Rourke
# Class of languages accepted by Python RegEx?

(Asked by: username_0 on 2017-02-24)

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?

**Tags:** fl.formal-languages
> **Comments:**
> **username_1**: From https://en.wikipedia.org/wiki/RE2_(software) it seems [PCRE](https://en.wikipedia.org/wiki/PCRE) can be exponential time. It also seems that Perl's RE might be Turing complete.  

---

## 1 answers

### Answer by username_2 on 2017-02-25. Score: 3

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](http://www.ccs.neu.edu/home/turon/re-deriv.pdf) 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](https://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html) 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.

> **Comments:**
> **username_0**: "The set of regular languages is also closed under these operations, and lookaround operations can be defined in terms of them." Excellent point!  
> **username_2**: 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](https://github.com/lucaswiman/revex/pull/2) where I introduced most of the functionality based on Brzozowski derivatives, and [here's the PR](https://github.com/lucaswiman/revex/pull/12) where I implement lookaround support.  

---

