PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 24

Sean L1 y L2 cualquier lenguaje libre de contexto y R cualquier lenguaje regular. Entonces, ¿cuál de las siguientes es correcta?

I. L1 ∪ L2 is context-free.
II. L1' is context-free.
III. L1-R is context-free.
IV. L1 ∩ L2 context-free.

(A) Solo I, II y IV
(B) Solo I y III
(C) Solo II y IV
(D) Solo I

Respuesta: (B)
Explicación: El lenguaje libre de contexto está cerrado bajo unión y diferencia con el lenguaje regular.
No se cierra bajo complementación e intersección. El complemento de CFL es lenguaje recursivo.

Cuestionario de esta pregunta