Donar $20 Donar $50 Donar $100 Donar mensualmente
 


Enviar respuesta 
 
Calificación:
  • 1 votos - 5 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
[Sintaxis y Semántica de los Lenguaje] Un ejercicio de Expresiones Regulares...
Autor Mensaje
pablit Sin conexión
Secretario General
Ex- Don Ramón
*******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 915
Agradecimientos dados: 143
Agradecimientos: 635 en 88 posts
Registro en: Apr 2010
Mensaje: #1
Question [Sintaxis y Semántica de los Lenguaje] Un ejercicio de Expresiones Regulares... Ejercicios y 1 más Sintaxis y Semántica de los Lenguajes
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.

(Este mensaje fue modificado por última vez en: 27-11-2015 22:59 por pablit.)
26-06-2013 15:40
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #2
RE: Duda con un ejercicio de Expresiones Regulares
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

[Imagen: v34BEFt.gif]
(Este mensaje fue modificado por última vez en: 26-06-2013 15:53 por gonnza.)
26-06-2013 15:48
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] gonnza recibio 1 Gracias por este post
pablit (28-06-2013)
pablit Sin conexión
Secretario General
Ex- Don Ramón
*******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 915
Agradecimientos dados: 143
Agradecimientos: 635 en 88 posts
Registro en: Apr 2010
Mensaje: #3
RE: Duda con un ejercicio de Expresiones Regulares
(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...

28-06-2013 00:59
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
gonnza Sin conexión
User Verde

*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 17.112
Agradecimientos dados: 763
Agradecimientos: 732 en 317 posts
Registro en: Mar 2010
BlogSpot Google+ YouTube
Mensaje: #4
RE: Duda con un ejercicio de Expresiones Regulares
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

[Imagen: v34BEFt.gif]
28-06-2013 10:08
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)



    This forum uses Lukasz Tkacz MyBB addons.