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

Considere los siguientes lenguajes:
L1 = {a ⁿ b ^m c ⁿ : m, n >= 1}
L2 = {a ⁿ b ⁿ c ²ⁿ : n >= 1}
¿Cuál de los siguientes es VERDADERO?
(A) Tanto L1 como L2 son independientes del contexto.
(B) L1 está libre de contexto mientras que L2 no está libre de contexto.
(C) L2 está libre de contexto mientras que L1 no está libre de contexto.
(D) Ni L1 ni L2 están libres de contexto.

Respuesta: (B)
Explicación:  

•

•

L2 no está libre de contexto. no. de b coincidirá con no. de a’s dejando c’s para que no coincidan con nadie … por lo que L2 no puede estar libre de contexto.

Esta solución es aportada por .

Cuestionario de esta pregunta