PUERTA | PUERTA-CS-2005 | Pregunta 56

Sea L1 un lenguaje recursivo y sea L2 un lenguaje recursivamente enumerable pero no recursivo. ¿Cuál de las siguientes es VERDADERA?

L1' --> Complement of L1
L2' --> Complement of L2 

(A) L1′ es recursiva y L2′ es enumerable recursivamente ( B
) L1 ′ es recursiva y L2′ no es enumerable recursivamente ( C
) L1 ′ y L2′ son enumerables recursivamente ( D
) L1 ′ es enumerable recursivamente y L2′ es

Respuesta recursiva : (B)
Explicación: Los lenguajes recursivamente enumerables se conocen como lenguajes de tipo 0 en la jerarquía de lenguajes formales de Chomsky. Todos los lenguajes regulares , libres de contexto, sensibles al contexto y recursivos son recursivamente enumerables (Fuente: http://en.wikipedia.org/wiki/Recursively_enumerable_language )

Los lenguajes recursivos están cerrados bajo complementación, pero recursivamente enumerables no están cerrados bajo complementación . Si un lenguaje L es recursivamente enumerable, entonces su complemento es recursivamente enumerable si y solo si L también es recursivo. Dado que L2 es recursivamente enumerable, pero no recursivo, L2′ no es recursivamente enumerable.
Cuestionario de esta pregunta