PUERTA | PUERTA CS 2021 | Conjunto 1 | Pregunta 15

Considere las siguientes declaraciones.

• S1: Cada gramática SLR(1) no es ambigua, pero hay ciertas gramáticas no ambiguas que no son SLR(1).
• S2: para cualquier gramática independiente del contexto, hay un analizador que tarda como máximo O(n ³ ) tiempo en analizar una string de longitud n.

¿Cuál de las siguientes opciones es la correcta?
(A) S1 es verdadero y S2 es falso
(B) S1 es falso y S2 es verdadero
(C) S1 es verdadero y S2 es verdadero
(D) S1 es falso y S2 es falso

Respuesta: (C)
Explicación: tipos de analizadores :

La afirmación (S1) es correcta.

Usando el algoritmo CYK podemos probar el problema de membresía de CFG. Se tarda como máximo O(n ³ ) tiempo para analizar una string de longitud n.

La afirmación (S2) también es correcta.

Cuestionario de esta pregunta