Las expresiones regulares Equivalencia

Question

¿Hay una manera de saber si dos expresiones regulares arbitrarias son equivalentes? Parece un problema complejo para mí, pero podría haber algún mecanismo de simplificación de DFA o algo?

Answer 1

Para probar la equivalencia se puede calcular el mínima DFA de las expresiones y compararlos.

Answer 2

Capacidad de prueba de la igualdad es una de las propiedades clásicas de expresiones regulares. (N. B. Esto no se sostiene si usted está realmente hablando de expresiones regulares de Perl o alguna otra técnica no regular superlanguage.)

Convierte tus RE a generalizada autómatas finitos A y B, a continuación, construir un autómata nueva A-B tal que los estados de aceptación de A tienen transiciones nulos a los estados iniciales de B, y que se invierten los estados de aceptación de B. Esto le da un autómata que acepta todas esas cadenas aceptadas por A, a excepción de todos los aceptados por B.

Haga lo mismo para B-A, y reducir tanto a pura AF. Si un FA no tiene estados de aceptación accesibles desde un estado de inicio entonces se acepta el lenguaje vacío. Si usted puede demostrar que tanto A-B y B-A están vacías, que has demostrado que A = B.

Edit Je, no puedo creer que nadie se dio cuenta del error gigantesco allí - una intencional, por supuesto :-p

El autómatas A-B como se describe aceptará esas cadenas cuyo primer medio es aceptado por A y cuyo medio segundo no es aceptado por B. Construcción del deseada A-B es un proceso ligeramente más complicado. No puedo pensar en él la parte superior de mi cabeza, pero sí sé que es bien definido (y probablemente implica la creación de estados para la representación de los productos de la aceptación de los estados en A y los estados no aceptar en B).

Answer 3

Esto realmente depende de lo que entendemos por expresiones regulares. Como los otros críticos señalaron, reduciendo ambas expresiones a sus tamaños mínimos de DFA debería funcionar, pero sólo funciona para las expresiones regulares puros.

Algunas de las construcciones utilizadas en las librerías de expresiones regulares en el mundo real (referencias hacia atrás en particular) les dan el poder para expresar idiomas que no son regulares, por lo que el algoritmo de DFA no funcionará para ellos. Por ejemplo, la expresión regular: ([a-z]*) \1 coincide con un doble ocurrencia de la misma palabra separadas por un espacio (a a y b b pero no b a ni a b). Esto no puede ser reconocido por un autómata finito en absoluto.

Answer 4

Estas dos hilos Perlmonks análisis de esta pregunta (en concreto, lea las respuestas de blokhead):

• satisfacibilidad comparativo de las expresiones regulares
• prueba de equivalencia de expresiones regulares