Cercando di trovare un algoritmo che prende 2 espressioni regolari e indica se sono equivalenti

Question

Sto cercando di scoprire quale algoritmo sarebbe stato dato due lingue L1 e L2 per determinare se sono equivalenti (L1 = L2) .

E 'sorprendentemente difficile a venire con uno come ho trovato, anche se io sono abbastanza sicuro che deve essere convertito in un DFA prima e poi ridurre ciascuno di loro per un minimo DFA ..

Inoltre, So che se L1 - L2 e L2 - L1 sono vuoti, allora L1 = L2.

Chiunque è bravo con la teoria qui?

Answer 1

È possibile trovare una descrizione di un algoritmo ragionevolmente efficiente per testare r.e. uguaglianza qui:

http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf

scavare attraverso i riferimenti di questo articolo per trovare altre soluzioni che possono essere meno efficiente, ma più facile da implementare.

Answer 2

Ecco una risposta concettualmente semplice (supponendo che L1 e L2 siano regolari).

1) Trova DFA D1 e D2 rispettivamente per L1 e L2.

2) Costruisci D'1 e D'2 da D1 e D2 scambiando stati di accettazione/non accettazione (nota che D'1 accetta esattamente ~ L1 e D'2 accetta ~ L2 dove ~ significa "complemento di")

3) Utilizzare la costruzione prodotto standard per tre volte per produrre un DFA che accetta esattamente (L1 intersecano ~ L2) unione (L2 intersecano ~ L1)

4) Verificare se il DFAE da parte 3 accetta qualsiasi stringa controllando ogni stato di accettazione per raggiungerlo dallo stato iniziale.

5) Se il DFA della parte 3 accetta qualsiasi stringa, quindi L1 <> L2. Altrimenti, L1 = L2

Esiste un numero enorme di euristiche che è possibile utilizzare per accelerare l'operazione, ma concettualmente, questo è probabilmente l'algoritmo più semplice. Un buon riferimento per la costruzione del prodotto nella parte 3 è "Automata e computabilità" di Dexter Kozen.