$\color{red}{\text{Detailed Video Solution, with Proof:}}$ https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=153s
Given $\Sigma = \{a,b \}$
A.
$\Sigma^*$, the set of all (finite length) binary strings over $\Sigma$, is countable.
Proof 1 (Video Explanation HERE):
We can create a bijection between $\Sigma^*$ and $\mathbb{N}$.
Assume $a = 0, b=1.$ Consider the mapping $f: \Sigma^* \rightarrow \mathbb{N}$, $f(w) = $ the decimal value of $1w.$
For example, $f(\epsilon) = $ decimal value of $1\epsilon = 1$; $f(00) = $ decimal value of $100 = 4$
This mapping $f$ is bijection from $\Sigma^*$ to $\mathbb{N}$. Hence, $\Sigma^*$ is countable.
NOTE: For EVERY alphabet $\Sigma$, the language $\Sigma^*$ is countable.
Two other ways to prove it are given HERE.
B.
For EVERY $\Sigma,$ the set of all languages is uncountable.
The set of all languages over $\Sigma$ is the powerset of $\Sigma^*$ i.e. $P(\Sigma^*).$
Proof:
By Cantor’s theorem, we know: If $S$ is ANY infinite set, then $P(S)$ is always uncountable. (Or we can say, NO infinite powerset is countable.)
Since, for every $\Sigma$, $\Sigma^*$ is infinite, hence, $P(\Sigma^*)$ is uncountable.
Learn Cantor’s Theorem & its Consequences HERE.
C.
For EVERY $\Sigma$, Set of ALL regular languages is countable.
For EVERY $\Sigma$, Set of ALL recursively enumerable languages is countable. Proof HERE
Since set of all RE languages is countable, & subset of countable set is countable; hence, set of regular languages is also countable.
D.
Set of all languages accepted by Turing machines is same as the set of all recursively enumerable languages.
For EVERY $\Sigma$, Set of ALL recursively enumerable languages is countable. Proof HERE
Countability Complete Course, with Proofs, Variations & All type of questions covered: https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared
