Expressões regulares e 'captura de parênteses' com 'referências anteriores'

Sabemos que expressões regulares (ER) são implementadas com autômatos finitos (FA). Em alguma linguagem (como JavaScript) no RE, existem recursos como 'capturando parênteses' com 'referências anteriores':

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions#special-capturing-parentheses

(x) Corresponde a 'x' e se lembra da correspondência, como mostra o exemplo a seguir. Os parênteses são chamados de captura de parênteses. Os '(foo)' e '(bar)' no padrão / (foo) (bar) \ 1 \ 2 / correspondem e lembre-se das duas primeiras palavras da string "foo bar foo bar". O \ 1 e \ 2 no padrão correspondem às duas últimas palavras da sequência.

Quero saber se esse padrão /(foo) (bar) \1 \2/é de fato um ER de acordo com a definição de ER que temos na linguagem formal teórica ou se é algo mais poderoso. E se é assim, eu gostaria de saber se esse tipo de recurso é implementado também com a FA ou de outra maneira (em particular como é implementado).

O ER na teoria dos autômatos é equivalente ao FA, mas para as linguagens de programação (regexp) isso não é mais verdade.

As expressões regulares nas linguagens de programação (como PCRE) são muito mais poderosas que as Expressões regulares (tipo 3) na Teoria dos Automata.

O parêntese correspondente não é regular nem isento de contexto, é um recurso sensível ao contexto. Mas o RegExp da pergunta não suporta totalmente o Tipo 2 ou o Tipo 1.

A correspondência de colchetes não é implementada via FA. No caso do PCRE, é implementado por adivinhação e retorno.

Dê uma olhada na descrição do Perl Monks sobre o PCRE .

Essas noções estendidas de expressões regulares capturam mais do que apenas as linguagens regulares. Por exemplo, ([ab]*)\1corresponde ao idioma , que não é regular e nem sequer é livre de contexto (Exemplo 2.38 de Sipser, Introdução à teoria de Computação , 3ª edição).$\{ww\mid w\in\{a,b\}^*\}$

Expressões "regulares" que não correspondem a idiomas regulares não podem ser traduzidas para autômatos finitos, pois os autômatos finitos correspondem apenas aos idiomas regulares. Um efeito colateral disso é que muitas bibliotecas nem tentam compilar para automatizar, o que pode levar a uma correspondência extremamente lenta, mesmo quando uma expressão "regular" é uma expressão regular verdadeira. Russ Cox escreveu um excelente artigo sobre isso, que também se passa em grande parte da história.

As respostas provavelmente estão respondendo ao que você pretende perguntar, mas não ao que está perguntando.

Quero saber se esse padrão /(foo) (bar) \1 \2/é de fato um ER de acordo com a definição de ER que temos na linguagem formal teórica ou se é algo mais poderoso. E se é assim, eu gostaria de saber se esse tipo de recurso é implementado também com a FA ou de outra maneira (em particular como é implementado).

Na verdade, esta é uma expressão regular que pode ser implementado com um autômato finito, porque \1é garantida para avaliar a fooe \2está garantido para avaliar a bar.

Portanto, um mecanismo de expressão regular poderia usar esse fato para criar um autômato finito que descreve exatamente o idioma que você propôs.

No entanto, se você condicionar as capturas , isso poderá se tornar falso, como outros já mencionaram.

(Observe que eu digo que você pode ter problemas, porque um idioma como ainda/(a(aa|aa)|(aa|aa)a)\1\2/ pode ser descrito por meio de uma FA. Eu apenas lhe dei uma condição necessária, e não suficiente. Edit: Apenas me ocorreu que ter uma condicional não é necessário nem necessário. suficiente, como também pode ser transformado em um autômato finito, embora não possa. /(a*)\1//(ab*)\1/

Determinada implementação de regex não cria um DFA. Por exemplo, a implementação do java.util.regex OpenJDK não. Como resultado, seu tempo de correspondência é mais lento que a implementação compilada pelo DFA, como dk.brics.automaton . No entanto, o posterior não suporta a captura de grupo como resultado da implementação subjacente.