[2022] [Primer Parcial] [Ejercicio 2] [Parte d]

[2022] [Primer Parcial] [Ejercicio 2] [Parte d]

de Ana Natalia Brum Betancurt -
Número de respuestas: 4

Hola!

La solución presentada, puede ser que este incorrecta? ya que reconoce la tira con 7 ceros al final , por lo tanto n mod 3 > 0, no cumpliendo con la definición.

Para contestar la parte d , mi solución es muy similar pero la transición del estado final va a q2 en lugar de q1 , podrian confirmarme si esta correcto?




En respuesta a Ana Natalia Brum Betancurt

Re: 1 parcial 2022 ejercicio 2d

de Diego Garat -
hola:

coincido contigo que, intuitivamente, la solución que estás presentando es mejor, porque modelar "tira de largo múltiplo de 3" se realiza como en tu solución.

sin embargo, ambas soluciones están bien, porque según la definición del leguaje, basta con que la tira termine con tres 1. fijate que, dada una tira con cualquier cantidad mayor de unos al final, se pueden "pasar" a la x del medio, que no tiene ninguna restricción, todos los unos menos los últimos tres. ergo, cualquier tira con (al menos) tres unos al final pertenece al lenguaje.

diría, entonces, que, a los efectos didácticos, en ambos autómatas sobra la transición saliente del estado final. sin embargo, estrictamente desde el punto de vista formal, ambos autómatas son correctos (y equivalentes).

saludos,
d.-
En respuesta a Diego Garat

Re: 1 parcial 2022 ejercicio 2d

de Ana Natalia Brum Betancurt -
Muchas gracias por tu respuesta.
Cometí un error a citar el contra ejemplo, lo que decir es que la tira que finaliza en 7 unos , es aceptada por el automata de la solución, y si bien termina con 3 unos , entiendo no cumple que n mod 3 = 0.

Esto es la tira : 01111111 entiendo que no pertenece a L2,

L2={0kx1n: k>0, n mod 3 = 0, n >0, x ∈ Σ*} y Σ = {0,1}

O quizás lo que me dices es que con n mod 3 = 0 hacían referencia a que terminara con 3 ceros consecutivos y no que la cantidad sea múltiplo de 3 ?

Muchas gracias!
En respuesta a Ana Natalia Brum Betancurt

Re: 1 parcial 2022 ejercicio 2d

de Diego Garat -
hola:

la formulación del lenguaje es tramposa: la tira 01111111 pertenece al lenguaje L2.

fijate que la puedo reescribir como:

01111111 = 0.1111.111 = 0^1.x.1^3 con x=1111

y por lo tanto, esa tira cumple las condiciones de pertenencia al lenguaje.

en general, esto sucede con cualquier cantidad de unos al final, porque siempre los puedo "pasar" a la x del medio. entonces, con que tengan al menos 3 unos al final, ya puedo garantizar que se cumple la condición n mod 3 = 0 (n>0). lo mismo sucede con los ceros del comienzo, basta con tener un cero, porque el resto pueden pasar a x si así lo quiero.

en definitiva, el lenguaje se podría reescribir como {0.x.111: x ∈ Σ*} y son las tiras que comienzan por un 0 y terminan con tres 1.

saludos,
d.-

pd: también podría haber dejado 6 unos al final para probar la pertenencia  0.1.111111 = 0^1.x.1^6 con x=1, pero a los efectos de ver cuál es realmente el lenguaje, es mejor usar solo 3 :)