Expresión Regular con Kleen y con Clases de Equiv

Expresión Regular con Kleen y con Clases de Equiv

de Favio Rafael Cardoso Sanchez -
Número de respuestas: 2

Buenas, hay algo que no entendí y es si la expresión regular hallada por el análisis de Kleene en un AFD sin minimizar es equivalente a la hallada luego de minimizar el autómata, hallar las expresiones regulares de sus estados y hacer el pipe de las expresiones regulares que definen sus estados finales.

Con equivalente quiero decir que ambas expresiones definen el mismo lenguaje.

Saludos!

En respuesta a Favio Rafael Cardoso Sanchez

Re: Expresión Regular con Kleen y con Clases de Equiv

de Diego Garat -
hola:

sí, son equivalentes. lo que describiste son dos formas de calcular una ER que denota al lenguaje que reconoce un AF... ahora bien, las ER obtenidas por uno y otro método no tienen que ser iguales sintácticamente, pero sí son equivalentes (denotan al mismo conjunto de tiras).

por las dudas aclaro que, "hallar las expresiones regulares de sus estados y hacer el pipe de las expresiones regulares que definen sus estados finales." es válido para todo autómata, no solo para el mínimo. ustedes pueden calcular RM de un AFD que no sea mínimo y obtener así la ER que denota al lenguaje.

el lenguaje reconocido por un autómata es único... la minimización genera una automáta mínimo equivalente, con lo que, al final del día, siempre estamos hablando del mismo lenguaje. hacer cualquiera de los cálculos sobre uno u otro autómata debería darles una ER equivalente.

saludos,
d.-