Esiste un modo per annullare un'espressione regolare?

Question

Data un'espressione regolare R che descrive un linguaggio normale (nessuna retrocessione di fantasia). Esiste un modo algoritmico per costruire un'espressione regolare R * che descrive la lingua di tutte le parole ad eccezione di quelle descritte da R? Dovrebbe essere possibile in quanto Wikipedia dice:

I linguaggi regolari sono chiusi sotto le varie operazioni, vale a dire, se le lingue K e L sono regolari, così è il risultato delle seguenti operazioni: [ ...] il complemento ¬L

Ad esempio, dato l'alfabeto {a, b, c}, l'inverso della lingua (abc *) + è (un | (ac | b | c). *)?

---

Come DPenner ha già sottolineato nei commenti, l'inverso di un expresion regolare può essere esponenzialmente più grande della espressione originale. Ciò rende l'inversione delle espressioni regolari inadatta per implementare la sintassi di espressioni parziali negative per scopi di ricerca. Esiste un algoritmo che conserva la O (n * m) runtime caratteristica (dove n è la dimensione della regex e m è la lunghezza dell'input) dell'espressione regolare corrispondente e consente una sottoespressioni negati?

Answer 1

Sfortunatamente, la risposta fornita da nhahdtdh nei commenti è buona quanto possiamo fare (finora). Se una determinata espressione regolare genera tutte le stringhe è completa con PSPACE. Poiché tutti i problemi in NP sono completati con PSPACE, una soluzione efficiente al problema dell'universalità implicherebbe che P = NP.

Se ci fosse una soluzione efficiente al tuo problema, saresti in grado di risolvere il problema dell'universalità? Certo che lo faresti.

1. Utilizzare l'algoritmo efficiente per generare un'espressione regolare per la negazione;
2. Determina se l'espressione regolare risultante genera il set vuoto.

noti che il problema "data un'espressione regolare, non genera l'insieme vuoto" è piuttosto semplice:

1. L'espressione regolare {} genera l'insieme vuoto.
2. (r + s) genera il set vuoto se entrambi i valori r e s generano il set vuoto.
3. (rs) genera il set vuoto se r o s genera il set vuoto.
4. Nessun altro genera il set vuoto.

Fondamentalmente, è abbastanza facile capire se un'espressione regolare genera il set vuoto: basta iniziare a valutare l'espressione regolare.

(Si noti che mentre la procedura sopra è efficiente in termini di lunghezza di uscita, potrebbe non essere efficiente in termini di lunghezza di input, se la lunghezza di uscita è più che polinomiale più veloce della lunghezza di input. se così fosse, avremmo comunque lo stesso risultato, cioè che il tuo algoritmo non è veramente efficiente, dal momento che richiederebbero in modo esponenziale molti passaggi per generare un output esponenzialmente più lungo da un dato input).

Answer 2

Wikipedia dice: ... if there exists at least one regex that matches a particular set then there exist an infinite number of such expressions. Possiamo dedurre da questa affermazione che esiste un numero infinito di espressioni che descrivono la lingua di tutte le parole eccetto quelle descritte da R.

Anche in questo caso, (come anche @nhahtdh ha cercato di spiegare) l'algoritmo più semplice per rispondere a questa domanda è estendere l'ambito della valutazione al di fuori del contesto del linguaggio delle espressioni regolari stesso. Ovvero: corrisponde alle stringhe che si desidera escludere (che rappresentano un sottoinsieme finito con cui lavorare) utilizzando l'espressione regolare originale e quindi trattare eventuali errori corrispondenti a una corrispondenza effettiva (su un insieme infinito di altre possibilità). Quindi, se il risultato della corrispondenza è negativo, le stringhe candidate sono un sottoinsieme delle soluzioni valide.