4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Sep 18, 2023 at 23:03
  • $\begingroup$ @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 σ. ? $\endgroup$
    – CoolCoder
    Nov 4, 2023 at 11:11
  • $\begingroup$ @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$. $\endgroup$ Nov 4, 2023 at 11:21

1 Answer 1

2
$\begingroup$

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.

$\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.