[T5] P1 Duda Conjunto especificado

[fprebolledo]

Hola!, no entendí muy bien la pregunta 1. Podrían dar un ejemplo del conjunto que se nos pide demostrar que es regular?

[crivero1]

Hola Francisca,

Considera la siguiente gramática:

X -> XX | a

Si haces una derivación por la izquierda de X, te darás cuenta que: X => X X^i con i el número de reglas que ocupaste. Por lo tanto LX será {X^i | i >= 0} = X*. Se entiende?

Suerte!

[bgsamilla]

Pero que pasa con la letra a, no se utiliza? No debería el lenguaje también tener las palabras conformadas por a y X?

[crivero1]

Hola Barbara,

No, la "a" no se usa en la definición. Mira como es la definición de una palabra en el lenguaje:

X =>_{lm} X \gamma

Y \gamma es una palabra del lenguaje L_X. Entonces la derivación por la izquierda debe terminar en el mismo X y por eso no usa la "a".

Saludos!

[fprebolledo]

Una pregunta! cuando dice que LX = {X^i | i >= 0} . i puede ser 0 ya que al partir con las primeras derivaciones se parte con la variable inicial verdad? por ejemplo la derivación 0 sería X, luego cuando elijo si X=XX o X=a es la primera verdad?

[cahinostroza]

Hola @fprebolledo , i puede ser 0 ya que para describir el lenguaje L_X, utilizamos la clausura refleja y transitiva de la derivación por la izquierda. Entonces también cuenta el no ejecutar ninguna producción o regla (lo que tu llamas derivación 0).

[VicenteVicente]

Hola Barbara,

No, la "a" no se usa en la definición. Mira como es la definición de una palabra en el lenguaje:

X =>_{lm} X \gamma

Y \gamma es una palabra del lenguaje L_X. Entonces la derivación por la izquierda debe terminar en el mismo X y por eso no usa la "a".

Saludos!

Hola me quedó una duda, entonces no podría haber hecho X => XX => Xa, cierto?, pues solo se deriva el de más a la izquierda?

Saludos!

[VicenteVicente]

Complementando la duda anterior, esto podría pasar? Gramática: X -> XX | XY Y -> aYb Producciones: X => XX X => XY X => XaYb X => Xaa...aaYbb...bb Es decir derivar no por la izquierda una variable distinta de X

[nicovsj]

Hola @VicenteVicente,

Si te fijas, las producciones que estás realizando no se pueden relacionar mediante derivaciones por la izquierda. Por ejemplo, en XY => XaYb no se cumple que la variable de más a la izquierda (X) fue la que se siguió derivando.

Así que es justo como dices en tu primera pregunta, no puedes tener algo del estilo X => XX => Xa si solo utilizas derivaciones por la izquierda.

[VicenteVicente]

Entiendo, muchas gracias 😄