Le espressioni regolari Equivalenza

Question

C'è un modo per scoprire se due espressioni regolari arbitrarie sono equivalenti? Sembra complesso problema per me, ma ci potrebbe essere qualche meccanismo di semplificazione DFA o qualcosa del genere?

Answer 1

Per verificare l'equivalenza è possibile calcolare la minimo DFA per le espressioni e confrontarli.

Answer 2

Testabilità di uguaglianza è una delle proprietà classiche di espressioni regolari. (N.B. Questo non vale se siete veramente parlando di espressioni regolari Perl o qualche altro tecnicamente non regolari superlinguaggio.)

Trasforma le tue RE al generalizzata finita automi A e B, quindi costruire un automa nuovo A-B in modo tale che gli stati che accettano di A hanno transizioni null per gli stati iniziali di B, e che gli stati che accettano di B sono invertite. Questo vi dà un automa che accetta tutte quelle stringhe accettate da A, ad eccezione di tutte quelle accettate da B.

Fare lo stesso per B-A, e ridurre sia alla pura FAS. Se un FA non ha stati accettare accessibile da uno stato di avvio allora accetta il linguaggio vuoto. Se si può dimostrare che sia A-B e B-A sono vuote, avete dimostrato che A = B.

Edit Eh, non posso credere che nessuno ha notato l'errore gigantesco lì - un uno intenzionale, naturalmente :-p

Gli automi A-B come descritto accetterà quelle corde la cui prima metà è accettato da A e il cui mezzo secondo, non è accettata da B. Costruire la desiderato A-B è un processo un po 'più complicato. Non riesco a pensare a lui fuori dalla parte superiore della mia testa, ma so che è ben definito (e probabilmente comporta la creazione membri alla rappresentare i prodotti di accettare stati in A e Stati non accettare in B).

Answer 3

Questo dipende da cosa si intende per le espressioni regolari. Come gli altri manifesti hanno sottolineato, riducendo sia le espressioni alle dimensioni minime DFA dovrebbe funzionare, ma funziona solo per le espressioni regolari puri.

Alcuni dei costrutti utilizzati nelle librerie regex del mondo reale (backreference in particolare) dare loro potere di esprimere lingue che non sono regolari, in modo da l'algoritmo DFA non funzionerà per loro. Ad esempio l'espressione regolare: ([a-z]*) \1 corrisponde una doppia occorrenza della stessa parola separate da uno spazio (a a e b b ma non b a né a b). Questo non può essere riconosciuto da un automa a stati finiti a tutti.

Answer 4

Queste due PerlMonks discussioni rispondono a questa domanda (in particolare, leggere le risposte di blokhead):

• soddisfacibilità comparativa delle espressioni regolari
• test di equivalenza regex