An infinite language has uncountably many subsets, while there are only countably many algorithms and therefore decidable languages. Thus some subset is undecidable, proving S1. Any finite language is a finite union of singleton-word regular expressions, proving S2. Both hold, C.
More Turing Machines and Undecidability questions
GATE 2026 CS (CS2) Q13– Which one of the following statements is equivalent to the assertion: Turing machine M…
GATE 2025 CS (CS2) Q25– Let G 1, G 2 be Context Free Grammars (CFGs) and R be a regular expression. For a grammar…