PUERTA | GATE-CS-2016 (Conjunto 2) | Pregunta 56

Un estudiante escribió dos gramáticas libres de contexto G1 y G2 para generar una sola declaración de array tipo C. La dimensión de la array es al menos uno. Por ejemplo,

int a[10][3]; 

Las gramáticas usan D como símbolo de inicio y usan seis símbolos de terminal int ; id [ ] núm.

Grammar G1
D → int L;
L → id [E
E → num]
E → num] [E

Grammar G2
D → int L;
L → id E
E → E[num]
E → [num] 

¿Cuál de las gramáticas genera correctamente la declaración mencionada anteriormente?

(A) Tanto G1 como G2
(B) Solo G1
(C) Solo G2
(D) Ni G1 ni G2

Respuesta: (A)
Explicación: gramáticas independientes del contexto

Una gramática libre de contexto (CFG) es un conjunto de reglas de reescritura recursivas (o producciones) que se utilizan para generar patrones de strings.

Un CFG consta de los siguientes componentes:
1) Un conjunto de símbolos terminales, que son los caracteres del alfabeto que aparecen en las strings generadas por la gramática.
2) Un conjunto de símbolos no terminales, que son marcadores de posición para patrones de símbolos terminales que pueden generar los símbolos no terminales.
3) Un conjunto de producciones, que son reglas para reemplazar (o reescribir) símbolos no terminales (en el lado izquierdo de la producción) en una string con otros símbolos no terminales o terminales (en el lado derecho de la producción).
4) Un símbolo de inicio, que es un símbolo no terminal especial que aparece en la string inicial generada por la gramática.

Para generar una string de símbolos de terminal desde un CFG, nosotros:
1) Comenzamos con una string que consiste en el símbolo de inicio;
2) Aplicar una de las producciones con el símbolo de inicio en el tamaño de la mano izquierda, reemplazando el símbolo de inicio con el lado derecho de la producción;
3) Repita el proceso de seleccionar símbolos no terminales en la string y reemplazarlos con el lado derecho de alguna producción correspondiente, hasta que todos los símbolos no terminales hayan sido reemplazados por símbolos terminales.

Dada una gramática G con el símbolo de inicio S, si hay alguna secuencia de producciones que, cuando se aplican a la string inicial S, dan como resultado la string s, entonces s está en L(G), el lenguaje de la gramática.

Necesitamos verificar cuál de las dos gramáticas genera correctamente «int a[10][3];». Esto significa que debemos comprobar si int id[num][num];

Grammar G1
D → int L;
L → id [E
E → num]
E → num] [E

Grammar G2
D → int L;
L → id E
E → E[num]
E → [num] 

Cuestionario de esta pregunta