Considere las siguientes afirmaciones sobre la gramática libre de contexto
G = {S → SS, S → ab, S → ba, S → Ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
¿Cuál de las siguientes combinaciones expresa todas las afirmaciones verdaderas sobre G?
(A) Solo I
(B) Solo I y III
(C) Solo II y III
(D) I, II y III
Respuesta: (B)
Explicación:
Declaración I: G es ambigua porque, como se muestra en la imagen a continuación, puede haber dos árboles de decisión para la string S = ababab [VERDADERO]
Declaración II: G produce todas las strings con el mismo número de a y b [FALSO]
la string ‘aabb’ no puede ser producida por G
Declaración III: G puede ser aceptado por un PDA determinista [VERDADERO]
Supongamos que hay un PDA que empuja si la parte superior de la pila es $(el alfabeto más bajo de la pila) y aparece en caso contrario. Se rechaza una string mientras se extrae si la letra actual y la parte superior de la pila son iguales. Este PDA puede derivar G.
Por lo tanto, la respuesta correcta debe ser (B) I y III solamente
Referencia:
Ambigüedad en gramática libre de contexto y lenguajes libres de contexto
Esta solución es aportada por .
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA