PUERTA | GATE-CS-2014-(Conjunto-3) | Pregunta 26

(A) A
(B) B
(C) C
(D) D

Respuesta: (C)
Explicación: Sea ∑ ={a, b}

entonces ∑* = { ε, a, b, aa, ba, bb, ……………….}

“Conjunto de todas las strings sobre cualquier alfabeto finito son contables ”. Por lo tanto, ∑* es contable.
Dado que existe un procedimiento de enumeración mediante el cual se puede generar toda la string del idioma, lo que significa que cada string se puede contar en un número finito de pasos.

Entonces, ∑* es contablemente infinito, pero 2 ^Σ* es incontable, lo que se puede probar usando el método de diagonalización. Este teorema dice: «Si ∑* es contablemente infinito, entonces 2 ^Σ* es incontable».

Cuestionario de esta pregunta