GATE 2014 CS (CS3) – Question 26

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice

Let $\Sigma$ be a finite nonempty alphabet and $2^{\Sigma^*}$ the power set of $\Sigma^*$. Which is TRUE?

Both $2^{\Sigma^*}$ and $\Sigma^*$ are countable.
$2^{\Sigma^*}$ is countable and $\Sigma^*$ is uncountable.
$2^{\Sigma^*}$ is uncountable and $\Sigma^*$ is countable.
Both $2^{\Sigma^*}$ and $\Sigma^*$ are uncountable.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $2^{\Sigma^*}$ is uncountable and $\Sigma^*$ is countable.

Explanation

For a finite nonempty alphabet, enumerate finite strings by length and then lexicographically, showing Σ*is countably infinite. Its power set is uncountable by Cantor’s theorem. Therefore **C**. Languages over the alphabet are subsets of the countable set of strings.