Sabía que al convertir una expresión regular en una NFA, hay un algoritmo.Cómo convertir NFA a la expresión regular
Pero me preguntaba si existe un algoritmo para convertir una NFA en expresión regular. Si hay, ¿qué es?
Y si no es así, también me pregunto si todos los NFA se pueden convertir a una expresión regular. ¿Hay un NFA que una expresión regular que no puede representar?
¡Gracias! : D
Aquí es un algoritmo donde cada transición se forma incremental reemplazado con una expresión regular, hasta que sólo hay un estado inicial y final: https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf [PDF]
es correcto pero no funciona si tienes muchos nodos, es bueno para un nodo simple y algunos nodos, ¿hay alguna otra sugerencia? –
El enlace está muerto para mí. Encontré este enlace pensado: https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf –
Una expresión regular puede expresar * cualquier lenguaje regular *, por lo que hay debería existir al menos una expresión regular para cada posible NFA. Sin embargo, no conozco un algoritmo para pasar de una NFA a una expresión regular fuera de mi cabeza. –
Además, su tiempo es realmente misterioso: mi amigo me hizo esta misma pregunta en clase hoy. Tampoco recuerdo la respuesta :( –
Vea una variedad de respuestas a su pregunta aquí: http://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular- expresiones – Masterfool