Question 46

Evaluate statement $S_1$:
Let $L$ be any infinite regular language over an alphabet $\Sigma$. Since $L$ contains countably infinitely many strings, the power set $2^L$ (the set of all sublanguages of $L$) is uncountably infinite, having cardinality $2^{\aleph_0}$. However, the set of all decidable (Turing-decidable) languages over $\Sigma$ is countably infinite, because every decidable language is decided by at least one valid Turing machine, and the set of all Turing machines is countable. Since a countably infinite set cannot contain an uncountably infinite set, uncountably many subsets of $L$ must be undecidable. Hence, $L$ contains undecidable languages as subsets. Statement $S_1$ is true.

Evaluate statement $S_2$:
Every finite language $L_{\text{fin}} = \{w_1, w_2, \dots, w_k\}$ is a finite union of single-string languages $\{w_i\}$. Each single-string language is trivially accepted by a finite automaton, and regular languages are closed under finite union. Therefore, every finite language is regular. Statement $S_2$ is true.

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