Solución:
Existen varios algoritmos para realizar esta tarea: el “método de eliminación de estados” de Brzozowski y Mc Cluskey, la resolución de un sistema de ecuaciones lineales, el método de McNaughton y Yamada, etc. Están muy bien descritos en Autómatas y expresiones racionales por Jacques Sakarovitch.
El método de eliminación de estados en particular es simple de entender. La idea clave es que vas a construir un autómata etiquetado por expresiones racionales (también conocidas como regulares) en lugar de letras. Primero, asegúrese de tener un solo estado inicial y un solo estado final (puede agregar estados nuevos y transiciones espontáneas si es necesario). Luego elija un estado s para eliminar, digamos el estado 1 en la siguiente imagen.
Luego considere todas las parejas (p, q) donde p es un predecesor (estados desde los cuales una transición llega a s, 0 en la imagen) y qa sucesor (estado 2). Para cada uno de esos pares (p, q) agregue una transición de p a q que está etiquetada por E (p, q) + E (p, s) E (s, s) * E (s, q) donde E (p , s) significa “la expresión que etiqueta la transición de p a s. Una vez que hayas tratado a todos los pares (p, q), elimina los estados s. En el ejemplo anterior:
Haga eso hasta que elimine todos los estados internos (es decir, mantenga el estado inicial y el estado final), y simplemente lea el resultado de la transición del estado inicial al estado final (aquí d + ab * c).
Puede jugar con este algoritmo usando Vcsn, una herramienta para expresiones racionales y autómatas. Aquí hay un ejemplo completo que puede reproducir en Vcsn Sandbox.
Creo que la mejor herramienta que he usado es greenery. Es una biblioteca de conversión FSM / regex para python. Puede leer más sobre la biblioteca aquí y el algoritmo utilizado se describe bien aquí.
Ejemplo
El modelo que se puede encontrar en el sitio web se puede convertir así:
from greenery import fsm, lego
A, B, C, D, E = range(5)
a, b = 'a', 'b'
# create the FSM
machine = fsm.fsm(
alphabet = {a, b},
states = {A, B, C, D, E},
initial = A,
finals = {C, E},
map = {
A : {a: B, b: D},
B : {a: C, b: E},
C : {a: C, b: E},
D : {a: B, b: D},
E : {a: B, b: D}
},
)
# convert it to regex
rex = lego.from_fsm(machine)
El resultado es el siguiente:
>>> print(machine)
name final? a b
------------------
* 0 False 1 3
1 False 2 4
2 True 2 4
3 False 1 3
4 True 1 3
>>> print(rex)
b*a((a*(a|b+))?ba)*(a+b?|b)
Nota
La versión en PYPI tiene algún problema con las afirmaciones, y la versión github tiene algunos problemas con la memoria, pero la combinación python 3.x + versión github es impresionante.
Puede usar fsm2regex, una herramienta en línea que hace el trabajo.