PUERTA | PUERTA CS 2010 | Pregunta 65 – Part 1

Sea L1 un lenguaje recursivo. Sean L2 y L3 lenguajes recursivamente enumerables pero no recursivos. ¿Cuál de las siguientes afirmaciones no es necesariamente cierta?
(A) L2 – L1 es recursivamente enumerable.
(B) L1 – L3 es recursivamente enumerable
(C) L2 ∩ L1 es recursivamente enumerable
(D) L2 ∪ L1 es recursivamente enumerable

Respuesta: (B)
Explicación:

A) Always True
(Recursively enumerable - Recursive ) is 
Recursively enumerable

B) Not always true
L1 - L3 = L1 intersection ( Complement L3 )
L1 is recursive , L3 is recursively enumerable 
but not recursive Recursively enumerable languages
are NOT closed under complement.

C) and D) Always true Recursively enumerable languages 
are closed under intersection and union. 

Cuestionario de esta pregunta