1
$\begingroup$

I understand that the number of languages that can be constructed from a given (non-empty) alphabet is uncountably infinite. I understand that this is because the kleene closure of a non-empty alphabet is countably infinite, and the set of all possible languages that can be constructed from that alphabet is the power set of the kleene closure of the alphabet. Cantor's diagonalization can then be used to show that the power set of an infinite set is uncountably infinite.

I am wondering if the set of all regular languages that can be constructed from a non-empty alphabet is countably or uncountably infinite. My intuition says uncountably infinite, but I can't figure out how to prove that, and I can't find an answer after spending an hour online.

$\endgroup$
1
  • $\begingroup$ Every regular language over $\Sigma$ is described by a regular expression over $\Sigma$. A regular expression is a finite string of symbols from $\Sigma$ together with symbols from a finite set that includes parentheses and a few operators. Provided that $\Sigma$ is countable, there are only countably many such strings and therefore only countably many regular languages. $\endgroup$
    – Brian M. Scott
    Oct 6, 2020 at 17:09

1 Answer 1

Reset to default
3
$\begingroup$

Every regular language corresponds to a finite automaton. So the set of regular languages is countable provided the alphabet is countable or finite (and not empty).

$\endgroup$
3
  • $\begingroup$ You are saying that the number of possible finite automata is countably infinite? If so, why? $\endgroup$
    – Denis
    Oct 6, 2020 at 16:03
  • $\begingroup$ A finite automaton is a finite graph. There are finitely many graphs with any given number of vertices. So the set of finite graphs is countable. The number of possible labelings of each finite graph is finite and the number of choices of input/accept states is finite. So the set of finite automata is countable. In fact it does not depend on the cardinality of the (nonempty) alphabet because you are interested in automata up to isomorphism. $\endgroup$
    – markvs
    Oct 6, 2020 at 16:13
  • $\begingroup$ That makes sense. Thank you. $\endgroup$
    – Denis
    Oct 6, 2020 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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