How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?

Question

I am struggling to answer the following question:

How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?

According to the textbook, the hint was to first calculate the number of 2-state DFAs over that alphabet and then see if any of those DFAs accept the same language.

I am able to calculate the number of 2-state DFAs over that alphabet (Because a DFA is defined as a quintuple $(Q, \Sigma, \delta, q_0, F)$, there are:

1. $Q$: 1 possibility (The number of states is already defined in the problem)
2. $\Sigma$: 1 possibility (The alphabet is already defined in the problem)
3. $\delta$: 4 possibilities (2 possible input states * 1 possible input character * 2 possible output states) = 4 possibilities)
4. $q_0$: 2 possibilities (The start state can be one of the 2 states)
5. $F$: 4 possibilities ($\emptyset$, $\{q_0\}$, $\{q_1\}$, $\{q_0, q_1\}$)

Total possibilities = 4 * 2 * 4 = 32. However, I am having trouble figuring out how many of the 32 DFA's accept the same language. The textbook says that there are 12 different DFAs that need to be considered due to symmetry, yielding 6 different languages—but I do not understand how the author got to that result.

Answer 1

There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that $Q = \{q_0,q_1\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here is one of them.

Case 1: $\delta(q_0,a) = q_0$. In this case we don't care about $\delta(q_1,a)$, since $q_1$ is unreachable. This case gives the two languages $\emptyset$ and $a^*$, depending on whether $q_0$ is a final state or not.

Case 2: $\delta(q_0,a) = q_1$. Since $F = \emptyset$ and $F = \{q_0,q_1\}$ will give the languages $\emptyset$ and $a^*$, respectively, it suffices to consider $F = \{q_0\}$ and $F = \{q_1\}$. Together, there are 4 machines to consider:

• $\delta(q_1,a) = q_1$, $F = \{q_0\}$: the language is $\epsilon$.
• $\delta(q_1,a) = q_1$, $F = \{q_1\}$: the language is $a^+$.
• $\delta(q_1,a) = q_0$, $F = \{q_0\}$: the language is $(aa)^*$.
• $\delta(q_1,a) = q_0$, $F = \{q_1\}$: the language is $a(aa)^*$.

These are the six different languages produced by unary two-state DFAs.