GATE CS 2014 Set 3 Q16 — Regular and Context-free Languages

To determine the countability of $\Sigma^*$ and $2^{\Sigma^*}$, let us analyze each set:

1. Countability of $\Sigma^*$:

   Since $\Sigma$ is a finite, non-empty alphabet, the set of all strings of a fixed length $k$ (denoted as $\Sigma^k$) is finite for any $k \ge 0$.

   The set $\Sigma^*$ is the union of these finite sets:

   $$\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k$$

   A countable union of finite sets is countably infinite. We can systematically list all strings in $\Sigma^*$ using lexicographical ordering (ordering by length, and then alphabetically for strings of the same length). This establishes a bijection with the set of natural numbers $\mathbb{N}$. Thus, $\Sigma^*$ is countable.

2. Countability of $2^{\Sigma^*}$:

   The set $2^{\Sigma^*}$ is the power set of $\Sigma^*$, which represents the set of all possible languages over the alphabet $\Sigma$.

   By Cantor's Theorem, the power set of any set $S$ has a strictly larger cardinality than $S$ itself ($|2^S| > |S|$).

   Since $|\Sigma^*| = \aleph_0$ (countably infinite), the cardinality of its power set is:

   $$|2^{\Sigma^*}| = 2^{\aleph_0} = c$$

   where $c$ is the cardinality of the continuum (the set of real numbers), which is uncountably infinite. Thus, $2^{\Sigma^*}$ is uncountable.

Therefore, $2^{\Sigma^*}$ is uncountable and $\Sigma^*$ is countable, which corresponds to Option C.