Dadas las siguientes afirmaciones:
S1: todo lenguaje sensible al contexto L es recursivo
S2: existe un lenguaje recursivo que no es sensible al contexto
¿Qué afirmaciones son verdaderas?
(A) Solo S1 es correcto
(B) Solo S2 es correcto
(C) Tanto S1 como S2 no son correctos
(D) Tanto S1 como S2 son correctos
Respuesta: (D)
Explicación: Según la jerarquía de Chomsky:
Referencia: Teoría de la computación | Los lenguajes CSL de la jerarquía de Chomsky
son el subconjunto de los lenguajes recursivos, por lo que (S1) es correcto.
Además, los lenguajes recursivos son el superconjunto de CSL y no es necesario que todos los lenguajes recursivos sean CSL. Entonces, (S2) también es correcto.
La opción (D) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA