regex - pal - ¿Existe un algoritmo que pueda determinar si un idioma regular coincide con alguna entrada, otro idioma regular coincide?

regular expression converter

Question

Digamos que tenemos expresiones regulares:

• Hola W. * rld
• Hola Mundo
• . * Mundo
• . * W. *

Me gustaría minimizar el número de expresiones regulares requeridas para coincidir con la entrada arbitraria.

Para hacerlo, necesito encontrar si una expresión regular coincide con alguna entrada que coincida con otra expresión. ¿Es eso posible?

Billy3

Answer 1

¡Por supuesto!. Una expresión regular puede representarse como un FSM (máquina de estados finitos) y existe un número técnicamente infinito de FSM que puede reconocer la misma cadena.

Isomorfismo es el nombre que describe si dos FSM son equivalentes. Hay un par de algoritmos para minimizar un FSM. Por ejemplo, el algoritmo de minimización de Hopcroft puede minimizar dos FSM en O (n log n), en un autómata de n estados.

Answer 2

Cualquier expresión regular puede vincularse a un DFA: puede minimizar el DFA y, como la forma mínima es única, puede decidir si dos expresiones son equivalentes. Dani Cricco señaló el algoritmo Hopcroft O (n log n). Hay otro algoritmo mejorado de Hopcroft y Craft que prueba la equivalencia de dos DFA en O (n).

Para una buena encuesta sobre el tema y un enfoque interesante para esto, recomiendo el documento Cómo probar la equivalencia de los idiomas regulares , de arXiv.

Edición posterior: si está interesado en la inclusión en lugar de la equivalencia para expresiones regulares, me he encontrado con un artículo que podría ser de interés: Problema de inclusión para expresiones regulares : solo lo he hojeado pero parece contener un algoritmo de tiempo polinomial para el problema.

Answer 3

Este problema se denomina "inclusión" o "subsunción" de expresiones regulares, porque lo que solicita es si el conjunto de palabras que coinciden con una expresión regular incluye (o subsume) el conjunto de palabras que coinciden con la otra expresión regular. La igualdad es una pregunta diferente que generalmente significa si dos expresiones regulares coinciden exactamente con las mismas palabras, es decir, que son funcionalmente equivalentes. Por ejemplo, "a *" incluye "aa *", mientras que no son iguales.

Todos los algoritmos conocidos para la inclusión de expresiones regulares son los peores casos de tiempo exponencial en el tamaño de la expresión regular. Pero el algoritmo estándar es así:

Entrada r1 y salida r2 Sí, si r1 incluye r2

1. Crear DFA (r1) y DFA (r2)
2. Crear Neg (DFA (r1)) (que coincide exactamente con las palabras r1 no coinciden)
3. Crear Neg (DFA (r1)) x DFA (r2) (que coincide exactamente con las palabras que coinciden con Neg (DFA (r1)) y DFA (r2))
4. Compruebe que el autómata hecho en 3. no coincide con ninguna palabra

Esto funciona, ya que lo que está comprobando es que no hay palabras que coincidan con r2 que no coincidan con r1.

Answer 4

Sí.

El problema de la equivalencia de dos lenguajes regulares es decidible.

Bosquejo de un algoritmo:

• minimizar ambos DFA
• comprueba si son isomorfos