PUERTA | PUERTA CS 2019 | Pregunta 43

Considere los siguientes conjuntos:

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

¿Cuáles de los conjuntos anteriores son incontables?
(A) S 1 y S 2
(B) S 3 y S 4
(C) S 1 y S 4
(D) S 2 y S 3

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

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *