Hola, tengo una duda con un ejercicio de Expresiones Regulares y no sé si está bien justificado...

La duda es la siguiente: ¿cómo demuestro que estas dos ERs son equivalentes: (a*+b*)* y ((ε+a)b*)*?


En clase un compañero sugirió la idea de hacer el autómata correspondiente a cada ER... y, si son iguales, determinar que sí son equivalentes.

El autómata es el siguiente, que sería el mismo para ambos:
Hace falta hacer/agregar algo más (por ejemplo, el "paso a paso" de cómo llegué a ese autómata) o con eso está bien demostrado?


Los leo. Y desde ya les agradezco.

si mal no recuerdo, para demostrar que 2 ER's son equivalente tenian que tener el mismo automata mínimo

si demostras que ambas ER llegan al mismo automata mínimo, y es el mismo, son iguales (la curse en 2010, asique apelo a mi memoria)


edit: Esto solo te sirve si ambas pueden ser reconocidas por un AFD

(26-06-2013 15:48)gonnza escribió:  si mal no recuerdo, para demostrar que 2 ER's son equivalente tenian que tener el mismo automata mínimo

si demostras que ambas ER llegan al mismo automata mínimo, y es el mismo, son iguales (la curse en 2010, asique apelo a mi memoria)


edit: Esto solo te sirve si ambas pueden ser reconocidas por un AFD

Claro, eso tengo entendido.
Haría paso por paso, digamos, explicando qué hago en cada uno para que se entienda...

claro, lo que tenes que mostrar es armar el automata para cada uno, y llegar al minimo.

Si el que armas ya es minimo, tendrias que demostrarlo (para cada uno)


luego si son iguales, son equivalentes