Prove that not all languages over unary alphabet are regular Let the alphabet be $\{0\}$. I have to prove that not all languages over this alphabet are regular, using some countability argument.
My Ideas:
The set of all languages over $\{0\}$ is uncountable. This can be proved with the diagonalization argument. So to prove the statement, I have to show that set of all regular languages over $\{0\}$ is countable. Not sure how to prove that.
You can show this in many ways. For example, every language can be defined using a regular expression, and the number of regular expressions over a fixed alphabet is countable, since a regular expression is just a word over some alphabet.