$L$ is a class of languages that cannot be represented by a regular expression. How to state cardinality of $L$.

Question

$L$ is a class of languages that cannot be represented by a regular expression.

The book says that the cardinality of $L$ is $2^{\aleph_0} > \aleph_0$

1. what's the logic behind getting the cardinality of $L$?

2. how does $|L| = 2^{\aleph_0}$?

thank you!!

Answer 1

Once you fix a finite alphabet $\Sigma$, the class of all language is $P(\Sigma^*)$ and has cardinality $2^{\aleph_0}$. Now, the regular languages $R$ are countable, since for instance regular expressions are countable (they can be encoded by words on a finite alphabet). But $L=P(\Sigma^*)\setminus R$. Since $|P(\Sigma^*)|=2^{\aleph_0}$ and $|R|=\aleph_0$ we get $|L|=2^{\aleph_0}$