Expressividade de expressões regulares modernas

9

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 ump grande o suficiente, existe kp de tal modo que p+nk é excelente para todos n1, 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 dek2ocorrências de |)n2vezes. Se corresponder, significa que o número representado pela sequência é divisível porke, 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.

yago
fonte
1
Pergunta relacionada . Parece que me lembro que pelo menos alguns sabores de RegExp são completos para Turing. Este artigo pode ser um ponto de partida válido para pesquisas na literatura.
Raphael
@Raphael Muito obrigado, o artigo parece responder a uma grande parte dos meus interrogatórios
Yago
Uma razão mais forte pela qual nem todos os p + nk podem ser primos é que, quando n = p, você tem p + nk = p (1 + k).
Nathan FD

Respostas: