PUERTA | GATE-CS-2014-(Conjunto-1) | Pregunta 45

Sea L una lengua y L’ su complemento. ¿Cuál de las siguientes NO es una posibilidad viable?

(A) Ni L ni L’ son recursivamente enumerables (re).
(B) Uno de L y L’ es re pero no recursivo; el otro no es re

(C) Tanto L como L’ son re pero no recursivos.
(D) Tanto L como L’ son recursivos

Respuesta: (C)
Explicación: A) Es posible si L mismo NO es RE. Entonces L’ tampoco será RE.
B) Supongamos que existe un lenguaje tal que la máquina de turing se detiene en la entrada. El lenguaje dado es RE pero no recursivo y su complemento NO es RE.
C) Esto no es posible porque si podemos escribir un procedimiento de enumeración para ambos lenguajes y su complemento, entonces el lenguaje se vuelve recursivo.
D) Es posible porque L es cerrado bajo complemento si es recursivo.
 
Por lo tanto, C es la opción correcta.
Cuestionario de esta pregunta