Consider the following sets: S1. Set of all recursively enumerable languages…
2019
Consider 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?
- A.
S1 and S2
- B.
S3 and S4
- C.
S2 and S3
- D.
S1 and S4
Attempted by 127 students.
Show answer & explanation
Correct answer: B
Answer: The uncountable sets are the set of all languages over {0,1} and the set of all non-regular languages.
Reasoning:
S3 (all languages over {0,1}): The set of all languages over the alphabet {0,1} is the power set of Σ*, where Σ* is countable. By Cantor's theorem, the power set of a countable set is uncountable, so this set is uncountable.
S4 (non-regular languages): There are only countably many regular languages because each can be described by a finite automaton or a regular expression (finite descriptions over finite alphabets). Removing this countable collection from the uncountable set of all languages leaves an uncountable set of non-regular languages.
S1 (recursively enumerable languages): Each recursively enumerable language can be described by a Turing machine or enumerator. Because there are only countably many Turing machines (finite strings encoding machines), the collection of recursively enumerable languages is at most countable.
S2 (syntactically valid C programs): Syntactically valid C programs are finite strings over a finite alphabet, so they form a countable set.
Conclusion: Only the set of all languages over {0,1} and the set of non-regular languages are uncountable.