GATE CS 2021 Set 2 Q36 — Regular and Context-free Languages

Let us analyze both statements individually:

• Statement $S_1$: Let $L$ be an infinite regular language. The power set of $L$, denoted as $\mathcal{P}(L)$, represents the set of all subsets of $L$. Since $L$ is infinite, $\mathcal{P}(L)$ is uncountably infinite ($2^{\aleph_0}$). However, the set of all decidable languages is countably infinite because each decidable language is decided by a distinct Turing machine, and the set of all Turing machines is countable. Since there are uncountably many subsets of $L$ but only countably many decidable languages, there must exist uncountably many subsets of $L$ that are undecidable. Thus, $S_1$ is true.


• Statement $S_2$: Any finite language $L = \{w_1, w_2, \dots, w_k\}$ can be defined by the regular expression $w_1 + w_2 + \dots + w_k$. Since a regular expression exists for every finite language, every finite language is regular. Thus, $S_2$ is true.

Since both statements $S_1$ and $S_2$ are true, the correct option is C.