[Ejercicio 5] [Parte 4]

[Ejercicio 5] [Parte 4]

de Diego Martin Amorena Gomez De Salazar -
Número de respuestas: 5

Buenas, llego a la siguiente formula en este ejercicio pero no se como seguir con la demostración.

x pertenece a L(r1) si x= (0 l1)^m 0 1^n

y pertenece a L(r2) si y=  1^n'  0 (0 l1)^m´


En respuesta a Diego Martin Amorena Gomez De Salazar

Re: Ej 4 a)

de Santiago Gongora -
Buenas tardes, Diego.

Como hay que probar que una expresión regular genera todas las tiras que genera la otra, la idea es probar la doble inclusión. Es decir:

  • probar que w \in L(1^∗0(0|1)^∗) \Longrightarrow w \in L((0|1)^∗01^∗)
  • y que w \in L((0|1)^∗01^∗) \Longrightarrow w \in L(1^∗0(0|1)^∗)
Para eso te sugiero que te tomes una tira genérica que pertenezca al lenguaje de la izquierda y luego pruebes que, por sus características, es generada por el lenguaje de la derecha.

Por ejemplo, podemos decir que si w \in L(1^∗0(0|1)^∗) entonces tiene la forma w=x0z donde x \in L(1^*) y z \in L((0|1)^*). Y de ahí podés empezar a transformar la expresión para llegar a algo que sepas que es generado por (0|1)^∗01^∗ ...

...quizás puedas plantear que si x \in L(1^*) entonces x \in L((0|1)^*), y ahí se empieza a parecer un poco más ;)

Con razonamientos de ese estilo, planteo de subtiras que conforman la tira original y operaciones de conjuntos, va saliendo :)

Esto también corre para el ejercicio 7.

Saludos,
Santi
En respuesta a Santiago Gongora

Re: Ej 4 a)

de Favio Rafael Cardoso Sanchez -
Buenas, intente poner en practica el pique que diste pero de lo unico que he podido darme cuenta es que ambos lenguajes estan incluidos en L ( (0 | 1)* )
esta inclusion es unidireccional, pues en los lenguajes no se encuentra epsilon, ni ninguna tira con solo 1s.

Gracias, Saludos
En respuesta a Favio Rafael Cardoso Sanchez

Re: Ej 4 a)

de Belen Brandino -
hola,
continuando con lo que dijo santi, teniamos una tira con la forma w = x0z , donde x \in L(1^*)   y llegamos a que  x \in L((0|1)^*) , que es exactamente lo que queremos, la primera parte del otro lenguaje, para llegar a que   x \in L((0|1)^*) y z \in L(1*) \Rightarrow w \in L((0|1)^*01^*))

entonces queda probar que z \in L(1^*) . partiendo de lo de santi, sabemos que  z \in L((0|1)^*) , y acá va otro pique, y es que podemos distinguir en casos, cuando z tiene 0's y cuando no. cuando no los tiene es trivial, en el caso que si los tenga podemos volver a proponer una tira genérica, en este caso fijando el último cero por ejemplo: z=a0b donde a \in L((0|1)^*) y b \in L(1^*) . con esto podes sustituir en el w original y ver cómo te queda la tira

cualquier cosa pregunta de nuevo,
saludos!
En respuesta a Belen Brandino

Re: Ej 4 a)

de Pedro Gonçalves Schwingel -
Buenas, puede ser que no tengamos que hacer induccion en este ejercicio? planteando las sugerencias para un x e y pertenecientes a los dos Lenguajes llegue a que x = y.
En respuesta a Pedro Gonçalves Schwingel

Re: Ej 4 a)

de Diego Garat -

hola: 

no sé cómo efectivamente habrás planteado la demostración, pero por lo que decís, te diría que no se puede probar así... si yo tomo dos elementos cualesquiera de un mismo conjunto, no necesariamente son lo mismo.

otra cosa sería probar la doble inclusión, como sugieren santiago y belén, en cuyo caso el uso de inducción suele ser una manera más elegante (y rápida) de probar ciertas cosas, aunque no necesariamente el único camino para esa demostración.

saludos,

d.-