Dadas dos expresiones regulares arbitrarias, ¿existe un algoritmo "eficiente" para determinar si coinciden con el mismo conjunto de cadenas?
De manera más general, ¿podemos calcular el tamaño de la intersección de los dos conjuntos de coincidencias?
¿Qué algoritmos existen para hacer esto y en qué clase de complejidad viven?
Si no permitimos la estrella de Kleene, ¿eso altera la imagen?
algorithms
regular-expressions
Orquídea matemática
fuente
fuente
Respuestas:
Hendrik Jan da una buena respuesta para la clase de complejidad, pero no un algoritmo en sí mismo.
El algoritmo más simple para hacer esto que conozco es convertir la expresión regular a un DFA. Existen técnicas conocidas para convertir una expresión regular en un NFA y un NFA en un DFA.
Una vez que tenga dos DFA, la prueba de equivalencia es eficiente y decidible, ya que la forma mínima de un DFA es única hasta el isomorfismo.
Sin embargo, construir estos DFA a partir de NFA podría llevar mucho tiempo y producir DFAS extremadamente grandes, exponencialmente grandes en el peor de los casos.
fuente
Se sabe que la equivalencia de las expresiones regulares es completa para PSPACE, lo cual es bastante malo. El documento "Complejidad de problemas de decisión para expresiones regulares simples" enumera varias subclases de expresiones regulares con sus respectivas complejidades. ( enlace )
fuente