PUERTA | Puerta TI 2007 | Pregunta 49

Considere las siguientes gramáticas. Los nombres que representan terminales se han especificado en letras mayúsculas. ¿Cuál de las siguientes afirmaciones es verdadera? (A) G ₁ no tiene contexto pero no es regular y G ₂ es regular (B) G ₂ no tiene contexto pero no es regular y G ₁ es regular (C) Tanto G ₁ como G ₂ son regulares (D) Ambos G ₁ y G ₂ no tienen contexto, pero ninguno de ellos es regular Respuesta: (D) Explicación: las gramáticas dadas se pueden reescribir como:

Digamos, while = w, expr =E, stmt = S, other = o
Aquí, podemos escribir una gramática lineal derecha para G ₁ como
S -> w(E)S
S -> o
E->ID

Entonces, L(G ₁ ) es regular.
Ahora para G ₂ también podemos escribir una gramática lineal derecha:
S -> w(E)S

E -> E+E
E -> E*E
S -> o
Pero en esta pregunta ambas gramáticas no son ni lineales a la derecha ni lineales a la izquierda.
Entonces, la opción (D) es correcta.
Cuestionario de esta pregunta