Onde a maioria das implementações REGEX se enquadram na escala de complexidade?

As implementações mais modernas de expressões regulares, como as em perl ou .NET, vão além da definição clássica de ciência da computação dos REGEXes com recursos como lookahead e lookbehind. Esses recursos permitem analisar instruções que não podem ser descritas com um autômato finito e não pushdown? Quanto mais perto de completar o processo isso os torna, se puderem?

Não acho que o problema real seja a questão do que significa ilimitado; isso não é pior do que qualquer outra situação na análise.

O problema está na caracterização de referências retrospectivas, que são muito poderosas e muito limitadas: elas permitem a descrição de algumas linguagens que não são livres de contexto, sem permitir algumas linguagens livres de contexto. Por exemplo, o regex (a*)b\1b\1corresponde a seqüências de caracteres do formato , e você pode usar o lema de bombeamento para mostrar que essa linguagem não é livre de contexto. No entanto, por outro lado, expressões regulares com referências anteriores não parecem suficientes para corresponder à linguagem de parênteses balanceada, que é a linguagem livre de contexto prototípica.$a^n \cdot b \cdot a^n \cdot b \cdot a^n$

É fácil o suficiente fornecer uma semântica denotacional dizendo o que são seqüências de caracteres em uma linguagem para expressões regulares, mas fornecer uma boa caracterização teórica de autômatos parece muito mais desafiadora. É algo como uma máquina de registro, em cujos registros você pode copiar substrings de sua entrada e com os quais você pode testar sua string atual, mas para a qual você não tem a capacidade de modificar esses registros.

As pessoas que fazem teoria de modelos finitos têm vários modelos de máquinas descolados, e seria interessante saber se isso corresponde a algum de seus modelos.

/(.*)\1/$L = \{ ww | w \in \Sigma^*\}$$w$$K$$L_K = \{ ww | w \in \Sigma^*, \mid w \mid \le K\}$$K$

Mas, em princípio, as regexps especificadas são mais poderosas que as linguagens regulares, pois essa pergunta relacionada discute com muito mais detalhes (com um exemplo bacana também).

Um resultado interessante, extraído dessa outra questão , também vinculada por Suresh Venkat, é que os regexps "Práticos" são NP-completos e, portanto, devem ter o equivalente em SAT em potência.

Sendo um especialista, embora eu concorde que intuitivamente "expressões regulares com referências anteriores não parecem suficientes para corresponder à linguagem equilibrada entre parênteses", há algo estranho acontecendo. A completude de NP implica que qualquer problema de NP pode ser polinomialmente reduzido a um regexp, portanto, provavelmente há apenas uma redução polinomial da linguagem "parênteses balanceados" para uma linguagem reconhecível com regexps. Mas, novamente, pode haver alguma regexp absurda para analisar uma CFL, pois ela pode até analisar números unários não primos!

Provavelmente, a lição é que as classes de complexidade e de linguagem não são comparáveis, em geral. O que também sugere reformular sua pergunta, referenciar a hierarquia de Chomsky em vez da "escala de complexidade" (mesmo que, para ser justo, eu não tenha ficado confuso com isso).

Charles Stewart escreve:

Aho, 1990, "Algoritmos para encontrar padrões em strings" mostra que o problema de associação para idiomas regulares com backtracking é NP completo.

Uma visualização parcial (pelo menos da declaração) pode ser encontrada no Google Livros , na página 289, e uma referência bibliográfica ao artigo pode ser encontrada aqui . Observe que, no documento, rewbr significa Expressão regular com referências posteriores.

PCRE, a implementação mais popular de "expressões regulares" também implementa padrões recursivos, que vão além das referências anteriores. Uma pergunta sobre sua complexidade acaba de ser feita no Stackoverflow. De acordo com a resposta prática do Perl guru brian d foy, isso torna o PCRE tão poderoso quanto as gramáticas sem contexto. No entanto, a sintaxe é péssima em comparação com a Forma Backus-Naur.