GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 2

Question

Which of the following statements is/are TRUE? (Mark all the appropriate choices)

• A. The set of all regular languages is countable
• B. The set of all context-free languages is countable
• C. The set of all recursive languages is countable
• D. The set of all recursively enumerable languages is countable

Comments

Turing Machines (TMs) can be represented as string encodings, which can be said to be subset of Σ*. Now, since Σ* is countable (we can think of a lexicographic enumerating sequence) and we also know that subset of a countable set is countable, hence set of TMs is countable.

Corresponding to every TM, we have an RE language, hence set of RE languages is also countable.

Answer 1

Recursively enumerable languages are accepted by Turing machines and we have a way to enumerate all possible Turing machines making them countable. Now $\textbf{any subset of a countable set is countable.}$ So, regular, context-free and recursive languages are also countable.
Reference: https://math.stackexchange.com/questions/19187/is-there-such-a-thing-as-a-countable-set-with-an-uncountable-subset