'Can PCREs match all context-sensitive languages?

It recently came to my attention that most programming languages' regex engines are not faithful implementations of regular expressions in the formal language theory sense. Features like lookahead and lookbehind features enable the matching of context-free grammars, a superset of regular grammars.

However, even more intriguingly, many regex engines can match certain context-sensitive languages. This article provides some examples: https://www.npopov.com/2012/06/15/The-true-power-of-regular-expressions.html#context-sensitive-grammars

The author questions whether PCRE can match all context-sensitive languages, as opposed to just some of them. Can anyone shed some light on this (preferably by way of a formal proof)?

regexpcrecontext-sensitive-grammarchomsky-hierarchy


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source

Related Questions