Seguimos buscando a Arshak. Ayudanos compartiendo!
Encuesta no oficial de docentes
Resultados de la encuesta no oficial de docentes
Probaste el SIGA Helper?

Donar $100 Donar $200 Donar $500 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
Presidente del CEIT
Tortuga marítima
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.084
Agradecimientos dados: 308
Agradecimientos: 1.441 en 145 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.

Viva Perón.
(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.356
Agradecimientos dados: 900
Agradecimientos: 887 en 356 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
Presidente del CEIT
Tortuga marítima
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.084
Agradecimientos dados: 308
Agradecimientos: 1.441 en 145 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...

Viva Perón.
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.356
Agradecimientos dados: 900
Agradecimientos: 887 en 356 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)