regex - probar - Expresiones regulares Equivalencia

expresiones regulares php

Question

¿Hay alguna forma de averiguar si dos expresiones regulares arbitrarias son equivalentes? Me parece un problema complejo, pero podría haber algún mecanismo de simplificación de DFA o algo así.

Answer 1

Esto realmente depende de lo que quieres decir con expresiones regulares. Como señalaron los otros carteles, la reducción de ambas expresiones a su DFA mínimo debería funcionar, pero solo funciona para las expresiones regulares puras.

Algunas de las construcciones utilizadas en las bibliotecas de expresiones regulares del mundo real (en particular, las referencias posteriores) les dan la capacidad de expresar idiomas que no son regulares, por lo que el algoritmo de DFA no funcionará para ellos. Por ejemplo, la expresión regular: ([az]*) /1 coincide con una doble aparición de la misma palabra separada por un espacio ( aa y bb pero no ba ni ab ). Esto no puede ser reconocido por un autómata finito en absoluto.

Answer 2

Estos dos hilos de Perlmonks discuten esta pregunta (específicamente, lea las respuestas de blokhead):

• Satisfabilidad comparativa de las expresiones regulares
• Prueba de equivalencia regex

Answer 3

Para probar la equivalencia, puede calcular los DFA mínimos para las expresiones y compararlos.

Answer 4

La capacidad de prueba de la igualdad es una de las propiedades clásicas de las expresiones regulares. (Nota: esto no se aplica si realmente está hablando de expresiones regulares de Perl o de algún otro superlenguaje técnicamente no regular).

Convierta sus RE en autómatas finitos generalizados A y B, luego construya un nuevo autómata AB de modo que los estados de aceptación de A tengan transiciones nulas a los estados de inicio de B, y que los estados de aceptación de B se inviertan. Esto le da un autómata que acepta todas las cadenas aceptadas por A, excepto todas aquellas aceptadas por B.

Haz lo mismo con BA, y reduce ambos a FAs puros. Si un FA no tiene estados aceptables accesibles desde un estado de inicio, entonces acepta el idioma vacío. Si puede mostrar que tanto AB como BA están vacíos, ha demostrado que A = B.

Edit Heh, no puedo creer que nadie notó el error gigantesco allí - uno intencional, por supuesto :-p

El autómata AB como se describe aceptará aquellas cadenas cuya primera mitad es aceptada por A y cuya segunda mitad no es aceptada por B. Construir el AB deseado es un proceso un poco más complicado. No puedo pensar en eso fuera de mi cabeza, pero sé que está bien definido (y probablemente implique crear estados para representar los productos de los estados aceptados en A y los estados no aceptables en B).