3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Hint: You can define an encoding for DFAs with a language. This language can also be over $\{0, 1\}$ (any language in $\{0, 1\}^\ast$ is countable). $\endgroup$
    – ttnick
    Apr 20, 2021 at 6:16

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.