PUERTA | PUERTA CS 1997 | Pregunta 19

Dado ∑ = {a, b}, ¿cuál de los siguientes conjuntos no es contable?
(A) Conjunto de todas las strings sobre ∑
(B) Conjunto de todos los idiomas sobre ∑
(C) Conjunto de todos los idiomas regulares sobre ∑
(D) Conjunto de todos los idiomas sobre ∑ aceptados por las máquinas de Turing

Respuesta: (B)
Explicación:

• (A) El conjunto ∑ ={a, b} es contable porque cada elemento de este conjunto se puede mapear con un número natural y también generar en el siguiente orden:
  Dado ∑ ={a, b}. Entonces, el orden será a,b,aa,ab,ba,bb,aaa,aab… Por lo tanto, se mapeará con un número natural. Por lo tanto, es contable .
• (B) Aquí, vemos que el conjunto de idiomas sobre z es el conjunto potencia de strings sobre ∑ que es un conjunto infinito y como sabemos que el conjunto potencia de un conjunto infinito es incontable. Por lo tanto, el conjunto de idiomas se convierte en un conjunto incontable a, por lo que podemos probar esto usando el método de diagonalización de Cantor.
• (C) El conjunto de todos los lenguajes regulares es un subconjunto del conjunto de todos los lenguajes recursivamente enumerables. Y sabemos que un subconjunto de un conjunto contable siempre es contable.
• (D) El conjunto de todos los lenguajes sobre ∑ aceptados por la máquina de Turing es contable.

La opción (B) es correcta.
Cuestionario de esta pregunta