PUERTA | Puerta TI 2007 | Pregunta 46

Las dos gramáticas dadas a continuación generan un lenguaje sobre el alfabeto {x, y, z} ¿Cuál de las siguientes opciones describe las propiedades que satisfacen las strings en estos lenguajes? (A) G1 : Ninguna y aparece antes de ninguna x G2 : Toda x va seguida de al menos una y (B) G1 : Ninguna y aparece antes de ninguna x G2 : Ninguna x aparece antes de ninguna y (C) G1 : Ninguna y aparece después cualquier x G2: cada x va seguida de al menos una y (D) G1: ninguna y aparece después de ninguna x G2: cada y va seguida de al menos una x Respuesta: (A) Explicación:

Para la pregunta anterior, podemos ver que para todas las opciones, las propiedades satisfechas por las strings podrían definirse como alguna relación entre los alfabetos x e y.
Para Grammar 1 , las strings con una combinación de x e y se pueden generar con la siguiente forma de producción de la gramática solamente.

S–>xS –>xyB o

S–>zS–>zxS–>zxyB

(En caso de que la producción inicial sea S–>x| z| yB, no puede dar tanto x como y en la string)
Por lo tanto, en cualquier string con x e y, ninguna y puede aparecer antes de que x pueda describirse como una propiedad satisfecha por la strings del lenguaje.

De manera similar, para Grammar 2 , las strings con una combinación de x e y se pueden generar con lo siguiente

forma de producción(es) de la gramática únicamente.

S–>yS –>yxB–>yxy O S–>yS –>yxB–>yxyB

S–>xB –>xy O S–>xB –>xyB

Por lo tanto, en cualquier string con x e y, cada x va seguida de al menos una y puede describirse como una propiedad satisfecha por las strings del lenguaje.

Esta solución es aportada por Yashika Arora .
Cuestionario de esta pregunta