TeoLeng: [Ejercicio 5] [Parte 4]

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´

Re: Ej 4 a)

de Santiago Gongora - martes, 15 de marzo de 2022, 17:30

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:

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

Re: Ej 4 a)

de Favio Rafael Cardoso Sanchez - jueves, 9 de marzo de 2023, 20:10

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

Re: Ej 4 a)

de Belen Brandino - lunes, 13 de marzo de 2023, 12:15

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!