Verifique se uma determinada regex corresponderá a qualquer coisa - regex, string, perl

É possível verificar se uma determinada expressão regular corresponderá a alguma string? Especificamente, estou procurando uma função matchesEverything($regex) que retorna iff verdadeiro $regex irá corresponder a qualquer string.

Suponho que isso equivale a perguntar ", dada uma expressão regular r, existe uma string que não corresponde r? "e eu não acho que isso possa ser solucionado sem colocar limites no conjunto de" todas as strings ". Ou seja, se eu presumir que as seqüências nunca conterão "blahblah", então eu posso simplesmente verificar se r corresponde a "bláblá". Mas e se não houver tais limites? Eu estou querendo saber se este problema pode ser resolvido verificando se o regex r é equivalente a .*.

Respostas:

Isso não responde exatamente à sua pergunta, mas espero que explique um pouco por que é difícil encontrar uma resposta simples:

Primeiro, o termo "regex" é um pouco obscuro, portanto, para esclarecer, temos:

• Expressões regulares "estritas", que são equivalentes a autômatos finitos determinísticos (DFAs).
• Expressões regulares compatíveis com Perl (PCREs), que adicionam vários toques e assobios, como lookaheads, backreferences, etc. Elas também são implementadas em outras linguagens, como Python e Java.
• Expressões regulares reais de Perl, que podem ficar ainda mais loucas, incluindo código Perl arbitrário, via ?{...} construir.

Eu acho que esse problema é solucionável por rigorososexpressões regulares. Você acabou de construir o DFA correspondente e pesquisar esse gráfico para ver se há algum caminho para um estado de não aceitação. Mas isso não ajuda no regex do "mundo real", que geralmente é PCRE.

Eu não acho que PCRE é Turing completo (embora eu não saiba - veja esta pergunta também: As regexes Perl estão completas?) Se fosse, acho que, como Jim Garrison comentou, esse é basicamente o problema da parada. Dito isso, também não é fácil transformá-los em um DFA, tornando o método acima inútil ...

Não tenho uma resposta para PCREs, mas esteja ciente de que as construções mencionadas (referências anteriores, etc.) dificultariam bastante, eu imagino. Embora eu hesite em dizer "impossível".

Um regex Perl genuíno com ?{...} é definitivamente Turing-completo, então existem dragões, e eu acho que você está sem sorte.