c++ - solucionario - teoria de automatas ejercicios resueltos

Biblioteca para verificar si dos expresiones regulares son iguales/isomorfas

Question

Necesito una biblioteca que tome dos expresiones regulares y determine si son isomorfas (es decir, que coincidan exactamente con el mismo conjunto de cadenas). Por ejemplo, a | b es isomorfo a [ab]

Tal como lo entiendo, una expresión regular se puede convertir en una NFA que, en algunos casos, se puede convertir de manera eficiente en una DFA. El DFA se puede convertir a un DFA mínimo, que, si lo comprendo correctamente, es único y, por lo tanto, estos DFA mínimos se pueden comparar para la igualdad. Me doy cuenta de que no todas las expresiones regulares NFA pueden transformarse de manera eficiente en DFA (especialmente cuando se generaron a partir de Perl Regexps que no son realmente "regulares"), en cuyo caso lo ideal sería que la biblioteca simplemente devolviera un error o alguna otra indicación de que la conversión es imposible.

Veo toneladas de artículos y artículos académicos en línea sobre cómo hacer esto (e incluso algunas asignaciones de programación para las clases que piden a los estudiantes que lo hagan) pero parece que no puedo encontrar una biblioteca que implemente esta funcionalidad. Preferiría una biblioteca de Python y / o C / C ++, pero una biblioteca en cualquier idioma funcionará. ¿Alguien sabe si tal biblioteca? Si no es así, ¿alguien sabe de una biblioteca que se acerque y que pueda usar como punto de partida?

Answer 1

La biblioteca de autómatas brics para Java también soporta esto. Puede convertir expresiones regulares a DFA con esto, verifique si son equivalentes.

Answer 2

No lo he intentado, pero Regexp:Compare con Perl parece prometedor: dos regex son equivalentes si el lenguaje del primero es un subconjunto del segundo y viceversa.