Expressividade de expressões regulares modernas

Recentemente, conversei com um amigo sobre um site que propunha desafios regex, combinando principalmente um grupo de palavras com uma propriedade especial. Ele estava procurando por um regex que corresponda a cadeias de caracteres como ||||||||onde o número de |é primo. Eu imediatamente disse a ele que nunca funcionaria, porque se esse idioma fosse regular, a tradução do lema de bombeamento daria o fato de que, para um$p$ grande o suficiente, existe $k \leq p$ de tal modo que $p + nk$ é excelente para todos $n \geq -1$, e bem, provavelmente não é esse o caso (repartição dos primos, trivialidade de uma propriedade tão desconhecida e esmagadora, ...)

Mas então alguém veio com a solução: não combinando (||+?)\1+ esta expressão tentativas para coincidir com o grupo de captura (que pode ser ||, |||, ||||e assim por diante de$k \geq 2$ocorrências de |)$n \geq 2$vezes. Se corresponder, significa que o número representado pela sequência é divisível por$k$e, portanto, não é primo. Caso contrário, é.

E eu me senti idiota, porque ficou óbvio que o agrupamento e a referência anterior permitem que o regex seja realmente muito mais expressivo do que ... a expressão regular, no sentido teórico. Agora, eles até adicionaram olhares e outros operadores que eu não conhecia quando fazia regex real.

Segundo a Wikipedia, é ainda mais expressivo que as linguagens geradas por uma gramática livre de contexto. Então aqui está a minha pergunta :

• podemos representar qualquer linguagem algébrica (gerada a partir de uma gramática livre de contexto) com modernos mecanismos de expressão regular
• existe uma descrição mais geral ou pelo menos um limite superior da complexidade de que tipo de linguagem pode ser descrita por um regex moderno?

Mais pragmaticamente, existe alguma teoria séria por trás dela ou estamos apenas adicionando novos recursos, uma vez que parece implementável no bloco inicial de expressões regulares reais baseadas em autômatos finitos?

Eu sei que "regex moderno" não é muito específico enquanto a pergunta é, mas quero dizer, pelo menos, com referências anteriores e possivelmente mais. Obviamente, se você tiver respostas parciais assumindo certas restrições nessa linguagem "regex moderna", sinta-se à vontade para publicá-la.

O problema da palavra expressões regulares com referências anteriores é NP-completo; citando Aho (1990) via Blaisorblade / Charles Stewart .

Não conheço todo o conjunto de operadores que alguns tipos de regexps possuem, mas vários não são mais poderosos que o normal ; eles provavelmente foram adicionados como açúcar sintático.