GATE CS 2014 Set 3 Q.26 (CS Q.16): Decidability, Reducibility and Undecidability

Let $\Sigma$ be a finite non-empty alphabet and let $2^{\Sigma^*}$ be the power set of $\Sigma^*$ . Which one of the following is TRUE?

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

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

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

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

Official answer and solution

Solution

Determine the cardinality of the language set Sigma* and its power set 2^(Sigma*) using set theory and Cantor's theorem.

Cardinality of $\Sigma^*$ :
- $\Sigma$ is a finite, non-empty alphabet (e.g., $|\Sigma| = k \ge 1$ ).
- $\Sigma^*$ is the set of all finite-length strings over $\Sigma$ : $\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n.$
- For each fixed length $n$ , the number of strings is $|\Sigma^n| = k^n$ , which is finite.
- Thus, $\Sigma^*$ is a countable union of finite sets, which is countably infinite (cardinality $\aleph_0$ ).
Cardinality of $2^{\Sigma^*}$ :
- $2^{\Sigma^*}$ is the power set of $\Sigma^*$ , which represents the collection of all possible languages over $\Sigma$ .
- By Cantor's theorem, the power set of any countably infinite set has cardinality $2^{\aleph_0} = \mathfrak{c}$ (the cardinality of the continuum).
- Since $2^{\aleph_0} > \aleph_0$ , $2^{\Sigma^*}$ is uncountably infinite.
Therefore, $2^{\Sigma^*}$ is uncountable and $\Sigma^*$ is countable (option C).

Final answer

Common trap

Confusing the countable infinitude of strings (Sigma*) with the uncountable infinitude of all possible languages (2^(Sigma*)).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.