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:
- Los lenguajes recursivamente enumerables son contables.
- El programa C sintácticamente válido se puede representar con CFG. CFG genera CFL, CFL es contable.
- Todos los idiomas por encima de {0, 1} pueden no ser contables, porque también pueden estar en la región de 2 Σ* .
- 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