# Deciding Countability of Languages

Suppose we have given $\Sigma=\{a,b\}$, Which one of the following set is not countable

(a) Set of all languages over $\Sigma$

(b) Set of all regular languages over $\Sigma$

(c) Set of all languages over $\Sigma$ accepted by Turing machine

I've read some techniques to find answer to the question like whether

Is the set of all infinite sequences of some alphabets countable or not

Is the set of all finite non-empty subsets of some alphabets countable or not

But they didn't helped me to answer questions like above. I tried Cantor Diagonalization but it didn't help either. How can we answer such questions.

• Hint: is the set of all Turing machines countable? Jan 11, 2015 at 18:13

Regular Language may be finite or infinite. Either case enumeration is possible as it contains pattern. Hence, Set of all regular languages over $\sum$ are Countable.
Since Language accepted by Turing Machine is Recursively Enumerable languages, As Enumeration is possible. Hence, Set of all languages over $\sum$ accepted by TM are Countable