PUERTA | Sudo GATE 2020 Mock III (24 de enero de 2019) | Pregunta 26

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

S → AB
A → aAb | ε
B → bBc | ε

(A) L = { un ^yo segundo ^j c ^k | yo, j, k ≥ 0, y yo+k > j }
(segundo) L = { un ^yo segundo ^j c ^k | yo, j, k ≥ 0, y i+j = k }
(C) L = { un ^yo segundo ^j c ^k | yo, j, k ≥ 0, y yo+k = j }
(D) L = { un ^yo segundo ^j c ^k | i, j, k ≥ 0 e i+j > k }

Respuesta: (C)
Explicación: En este caso, lo primero que observamos es que aún podemos aceptar la string vacía al establecer A y B como ε.

Luego, construimos la string usando nuestras variables A y B.
La variable A aquí asegura que tenemos el mismo número de a y b para cada aparición de A.
La variable B nos permite tener el mismo número de b y c, por cada aparición de B.

Por lo tanto, el número de b es la suma del número de a y c

L = { un ^yo segundo ^j c ^k | i, j, k ≥ 0 y i+k = j }

La opción (C) es correcta.
Cuestionario de esta pregunta