PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 26

Identifique el lenguaje generado siguiendo la gramática donde S es la variable de inicio.

S --> XY
X --> aX | a
Y --> aYb | ∈

(A) {un ^metro segundo ^norte | m>=n, n>0 }
(B) {a ^m b ⁿ | m>=n, n>=0 }
(C) {a ^m segundo ^norte | m>n, n>=0 }
(D) {a ^m b ⁿ | m>n, n>0 }

Respuesta: (C)
Explicación:

S --> XY
X --> aX | a  // This produces only "a"
Y --> aYb | ∈  // This produces and "a" for every "b"                     

Las opciones (A) y (B) son incorrectas porque n puede ser cero también
debido a épsilon en Y

La opción (D) es incorrecta porque Y–>aYb produce el mismo número de a y b.
Como hay una variable X que produce al menos una a.
Por lo tanto, los números de a son siempre mayores que los números de b.
Cuestionario de esta pregunta