Intentando encontrar un algoritmo que tome 2 expresiones regulares y diga si son equivalentes

Question

Estoy tratando de averiguar cuál sería el algoritmo al recibir dos idiomas L1 y L2 para determinar si son equivalentes (L1 = L2) .

Es sorprendentemente difícil llegar a una, ya que he encontrado, aunque estoy bastante seguro de que necesita ser convertido a un DFA primero y luego reducir cada uno de ellos a un mínimo de DFA ..

Además, Sé que si L1 - L2 y L2 - L1 están vacíos, entonces L1 = L2.

¿Alguien bueno con la teoría aquí?

Answer 1

Puede encontrar una descripción de un algoritmo razonablemente eficiente para probar r.e. la igualdad aquí:

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

excavar a través de referencias del artículo para encontrar otras soluciones que pueden ser menos eficiente, pero más fácil de implementar.

Answer 2

Aquí hay una respuesta conceptualmente simple (asumiendo que L1 y L2 son regulares).

1) Encuentra DFAs D1 y D2 para L1 y L2 respectivamente.

2) Construya D'1 y D'2 desde D1 y D2 intercambiando estados de aceptación/no aceptación (tenga en cuenta que D'1 acepta exactamente ~ L1 y D'2 acepta ~ L2 donde ~ significa "complemento de")

3) Usar la construcción del producto estándar tres veces para producir un AFD que acepte exactamente (L1 se cruzan ~ L2) unión (L2 se cruzan ~ L1)

4) comprobación para ver si el DFA de la parte 3 acepta cualquier cadena comprobando cada estado de aceptación para la accesibilidad desde el estado de inicio.

5) Si el DFA de la parte 3 acepta cualquier cadena, entonces L1 <> L2. De lo contrario, L1 = L2

Hay una gran cantidad de heurísticas que puede utilizar para acelerar esto, pero conceptualmente, este es probablemente el algoritmo más simple. Una buena referencia para la construcción del producto en la parte 3 es "Automata and Computability" de Dexter Kozen.