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

Considere los siguientes tipos de lenguajes:

L1 Regular,
L2: Context-free,
L3: Recursive,
L4: Recursively enumerable. 

¿Cuál de las siguientes es/son VERDADERAS?

I.   L3' U L4 is recursively enumerable
II.  L2  U L3 is recursive
III. L1* U L2 is context-free
IV.  L1 U L2' is context-free 

(A) Yo solo

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

Respuesta: (D)
Explicación: St 1: Como L3 es recursivo y los lenguajes recursivos están cerrados bajo complementación, L3′ también será recursivo y por lo tanto RE. L3′ U L4 también es enumerable recursivo ya que los lenguajes enumerables recursivos están cerrados bajo unión.
St 2: como L2 es libre de contexto, también será recursivo. L2 U L3 es recursivo porque como lenguajes recursivos están cerrados bajo unión.
St 3: L1* es regular porque los lenguajes regulares están cerrados bajo kleene –clausura. L1* U L2 es libre de contexto como unión de regular y libre de contexto es libre de contexto.
St 4:L2 ‘puede o no estar libre de contexto porque CFL no está cerrado bajo complementación. Así que no es cierto.

Entonces I, II y III son correctas.

Cuestionario de esta pregunta