Let $D=\left(Q, \Sigma, \delta, q_{0}, F\right)$ be a deterministic finite-state automaton (DFA). Define what it means for two states of $D$ to be equivalent. Define the minimal DFA $D / \sim$ for $D$.

Let $D$ be a DFA with no inaccessible states, and suppose that $A$ is another DFA on the same alphabet as $D$ and for which $\mathcal{L}(D)=\mathcal{L}(A)$. Show that $A$ has at least as many states as $D / \sim$. [You may use results from the course as long as you state them clearly.]

Construct a minimal DFA (that is, one with the smallest possible number of states) over the alphabet $\{0,1\}$ which accepts precisely the set of binary numbers which are multiples of 7. You may have leading zeros in your inputs (e.g.: 00101). Prove that your DFA is minimal by finding a distinguishing word for each pair of states.