What is the minimum DFA of this?

Question

I've been struggling for hours with this DFA, what I want to do is that get the minimum DFA of this. But whenever I'm trying to minimize this then I get a DFA the same as this.

Answer 1

The DFA is already minimal. To see why, we will show that for every two states $q_1$ and $q_2$, there is a word $x$ that separates between them. That is, there is a word $x$ such that one of the states $\delta^*(q_1, x)$ and $\delta^*(q_2, x)$ is accepting and the other is rejecting. To begin with, the rejecting and accepting states are separated via the empty word $\epsilon$ as $\delta^*(q, \epsilon) = q$, for every state $q$. So, the states $\{ A, C, D, G\}$ are separated from the states $\{ B, E, F, H\}$. The following holds:

1. $A$ is separated from $C, D, G$: $x = 1$ separates between $A$ and $C$. $x = 11$ separates between $A$ and $D$. Also, $x = 1$ separates between $A$ and $G$.

2. $C$ is separated from $A, G, D$: we've seen in item 1 that $C$ and $A$ are separated. $x = 011$ separates between $C$ and $G$. Also, $x = 01$ separates between $C$ and $D$.

3. $D$ is separated from $A, C, G$: we've seen in item $1$ that $D$ and $A$ are separated, and we've seen in item $2$ that $D$ and $C$ are separated. Finally, $D$ and $G$ are separated by $x = 1$.

4. $G$ is separated from $A, C, D$: we have seen that in the previous items.

5. $B$ is separated from $E, F, H$: $x = 0$ separates between $E$ and $B$. $x= 10$ separates between $F$ and $B$. Also, $x = 1$ separates between $B$ and $H$.

6. $E$ is separated from $B, F, H$: we have seen in item 5 that $E$ and $B$ are separated. $E$ and $F$ are separated by $x=1$. Also, $E$ and $H$ are separated by $x=0$.

7. $F$ is separated from $B, E, H$: we have seen in items 5 and 6 that $F$ is separated from $B$ and $E$. Finally, $x = 1$ separates between $F$ and $H$.

8. $H$ is separated from $B, E, F$: we have seen that in the previous items.