C'è un modo per scoprire se due espressioni regolari arbitrarie sono equivalenti? Mi sembra un problema complesso, ma potrebbe esserci qualche meccanismo di semplificazione di DFA o qualcosa del genere?Espressioni regolari Equivalenza
Per testare l'equivalenza è possibile calcolare la minimal DFAs per le espressioni e confrontarli .
Questi fili due PerlMonks discutere questa domanda (in particolare, leggere le risposte di blokhead):
La verificabilità dell'uguaglianza è una delle proprietà classiche delle espressioni regolari. (NB: questo non vale se siete veramente parlando di espressioni regolari Perl o qualche altro tecnicamente non regolari superlinguaggio.)
trasformare il vostro RE al generalizzata automi a stati finiti A e B, quindi costruire un nuovo automa AB tale che gli stati accettanti di A hanno transizioni nulle agli stati iniziali di B, e che gli stati accettanti di B sono invertiti. Questo ti dà un automa che accetta tutte quelle stringhe accettate da A, ad eccezione di tutte quelle accettate da B.
Fai lo stesso per B-A e riduci entrambi a FA puri. Se un FA non ha stati accettanti accessibili da uno stato di avvio, accetta la lingua vuota. Se riesci a dimostrare che AB e BA sono vuoti, hai dimostrato che A = B.
Edit Heh, non posso credere che nessuno abbia notato il gigantesco errore lì - intenzionale, ovviamente: - p
L'automa AB come descritto accetta quelle stringhe il cui primo tempo è accettato da A e la cui seconda metà non è accettata da B. Edificio desiderato AB è un processo leggermente più complicato. Non riesco a pensarci bene, ma so che è ben definito (e probabilmente implica la creazione di stati per rappresentare i prodotti di accettare stati in A e stati non accettanti in B).
Per A-B si desidera utilizzare invece l'intersezione e il complemento, che purtroppo non sono comuni nelle librerie di espressioni regolari, sebbene siano implementabili per espressioni regex "reali" (anziché per il tipo Perl). (Nemmeno sta testando se una regex non accetta nulla. Le biblioteche fanno schifo, vero?) –
Questo dipende molto da cosa intendi per espressioni regolari. Come hanno sottolineato gli altri utenti, la riduzione di entrambe le espressioni al loro DFA minimo dovrebbe funzionare, ma funziona solo per le espressioni regolari pure.
Alcuni dei costrutti utilizzati nel mondo reale regex libs (in particolare le sottorappresentazioni) danno loro la possibilità di esprimere linguaggi non regolari, quindi l'algoritmo DFA non funzionerà per essi. Ad esempio la regex: ([a-z]*) \1 corrisponde a una doppia occorrenza della stessa parola separata da uno spazio (a a e b b ma non b a né a b). Questo non può essere riconosciuto da un automa finito affatto.
cosa intendi con il confronto di due DFA? Isomorfismo grafico? – damned
Poiché si dispone di uno stato iniziale e le transizioni sono etichettate e deterministiche, è facile controllare i DFA per l'uguaglianza, molto più facilmente dell'isomorfismo grafico. Una traversata in profondità dovrebbe essere sufficiente. – starblue
@starblue Ottimo link! – Mooncrater