Project ForgeConsider the following sets:
S1. Set of all recursively enumerable languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet {0,1}
S4. Set of all non-regular languages over the alphabet {0,1}Which of the above sets are uncountable?
- AS1 and S2
- S3 and S4
- CS2 and S3
- DS1 and S4
Explanation
S1 (RE languages) and S2 (C programs) are both COUNTABLE, since each corresponds to a finite description (a Turing machine, or a finite source-code string) over a finite alphabet, and there are only countably many finite strings. S3, the set of ALL languages (i.e. the full power set of the countably infinite set Σ*), is UNCOUNTABLE by Cantor's theorem. S4 (non-regular languages) is also UNCOUNTABLE: since regular languages are countable (only countably many DFAs), removing a countable set from the uncountable S3 still leaves an uncountable set.
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.