Is the set of all DFAs countable?

Let $$\Sigma$$ be a finite nonempty alphabet. Is the set of all DFAs over $$\Sigma$$ countable?

I know the set of all regular languages is countable, however, it is impossible to build an injection from the DFAs to the regular languages since a regular language isn't necessarily accepted by only a single DFA.

• Let $|\Sigma|=n$ and consider the DFA’s with $m$ states. For each of the $mn$ state-symbol pairs $(S, \sigma)$, there are $m+1$ possibilities for the arc from $S$ that’s labeled $\sigma$. You should be able to take it from here. Sep 18, 2023 at 23:03
• @PaulTanenbaum can you explain in a little depth, the sentence 'For each of the mn state-symbol pairs (S,σ), there are m+1 possibilities for the arc from S that’s labeled σ. ? Nov 4, 2023 at 11:11
• @CoolCoder, if there is an arc, then it can point into any of the $m$ states, including looping back to the same state. But there may also not exist any arc out of a state for a given symbol. Consider a DFA that accepts the language $(ab)\ast$. A state reached upon reading an $a$ will not have an outbound arc for $a$. Nov 4, 2023 at 11:21

There are several ways to prove this. Here is a formal one:

You can encode the set of DFAs over $$\Sigma$$ as words over the constant alphabet $$\Sigma' = \{0, 1, \#\}$$. This can be done as follows. Let $$A = \langle \Sigma, Q, q_0, \delta, F\rangle$$ be a DFA over $$\Sigma$$. We define the encoding of $$A$$, denoted $$\langle A\rangle$$, as follows: $$\langle A\rangle = \langle \Sigma\rangle \#\# \langle Q\rangle \#\# \langle q_0\rangle \#\# \langle \delta\rangle\#\# \langle F\rangle,$$ where $$\langle C\rangle$$ is an encoding of $$C$$ over $$\Sigma'$$, for all $$C\in \{ \Sigma, Q, q_0, \delta, F \}$$, to be defined below.

We distinguish between several cases:

• $$C = \Sigma$$: we can encode the letters in $$\Sigma$$ as increasing binary numbers over $$\{ 0, 1\}$$. For example, if $$\Sigma = \{ a_0, a_1, \ldots, a_7\}$$, then we encode $$a_i$$ as the binary representation of the number $$i$$, and so $$\langle a_i \rangle = \text{the binary representation of the number i}$$. Then, we take $$\langle \Sigma \rangle = \langle a_0\rangle\# \langle a_1\rangle \# \cdots \# \langle a_7\rangle = 000\# 001 \# \cdots \#111$$ so the $$\#$$'s seprate between different letters.

• $$C = Q$$: also here, we can encode the states in $$Q$$ as increasing binary numbers.

• $$C = q_0$$: already encoded in the previous item. Let's say we encoded $$q_0$$ as the number 0 in binary.

• $$C = \delta$$: the encoding of $$\delta$$ can be simply a list of the transitions in $$\delta$$ separated by $$\#\#\#$$: $$\langle \delta\rangle = \langle t_1\rangle \#\#\#\langle t_2\rangle\#\#\# \cdots \#\#\# \langle t_k \rangle,$$ where $$t_i$$ is the $$i$$'th transition of $$A$$. So it remains to show how we encode a general transition. A transition $$t = q \xrightarrow{a} s$$ can be encoded as $$\langle t\rangle=\langle q \rangle \# \langle a\rangle\# \langle s\rangle$$. Note that we already encoded states and letters, so the latter is well-defined.

• $$C = F$$: since we already encoded the set of states $$Q$$, $$\langle F\rangle$$ can be simply encoded as the list of numbers describing the states in $$F$$ separated by $$\#$$'s.

What we've in total is a description of the DFA $$A$$ as a finite word over the constant alphabet $$\Sigma'$$. As the set $$\Sigma'$$ is countable, then there are at most $$\aleph_0$$ DFAs over $$\Sigma$$.

Note: the format of the encoding can be different. Its just one naive way to do it. The idea is to encode a DFA by an object that you know has countably many instances.