PUERTA | PUERTA-CS-2007 | Pregunta 78

Considere el CFG con {S,A,B) como el alfabeto no terminal, {a,b) como el alfabeto terminal, S como el símbolo de inicio y el siguiente conjunto de reglas de producción

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA

¿Cuál de las siguientes strings es generada por la gramática?
(A) aaaabb
(B) aabbbb
(C) aabbab
(D) abbbba

Respuesta: (C)
Explicación: Dadas las siguientes reglas de producción.

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA

Podemos derivar aabbab usando la siguiente secuencia

S  -> aB      [Using S --> aB] 
   -> aaBB    [Using B --> aBB]
   -> aabB    [Using B --> b]
   -> aabbS   [Using B --> bS]
   -> aabbaB  [Using S --> aB]
   -> aabbab  [Using B --> b]

Cuestionario de esta pregunta