PUERTA | PUERTA CS 2019 | Pregunta 43

Considere los siguientes conjuntos:

• S ₁ : Conjunto de todos los lenguajes recursivamente enumerables sobre el alfabeto {0, 1}.
• S ₂ : Conjunto de todos los programas en C sintácticamente válidos.
• S ₃ : Conjunto de todos los idiomas sobre el alfabeto {0, 1}.
• S ₄ : Conjunto de todos los idiomas no regulares sobre el alfabeto {0, 1}.

¿Cuáles de los conjuntos anteriores son incontables?
(A) S ₁ y S ₂
(B) S ₃ y S ₄
(C) S ₁ y S ₄
(D) S ₂ y S ₃

Respuesta: (B)
Explicación:

1. Los lenguajes recursivamente enumerables son contables.
2. El programa C sintácticamente válido se puede representar con CFG. CFG genera CFL, CFL es contable.
3. Todos los idiomas por encima de {0, 1} pueden no ser contables, porque también pueden estar en la región de 2 ^Σ* .
4. El conjunto de idiomas regulares son contables, los idiomas no regulares pueden no ser contables.

La opción (C) es verdadera.
Cuestionario de esta pregunta