\begin{frame}{Minimal DFAs (Hopcroft, 1971)} \begin{goal}{Goal} Given a DFA $M=(Q,\Sigma,\delta,q_0,F)$. \medskip Construct the (unique) \emph{minimal DFA} $\widehat{M}$ with $L(M) = L(\widehat{M})$.\\ \end{goal} (Here minimal is with respect to the number of states.) \pause\medskip \begin{construction} \emph{Step 1:} Remove all unreachable states from $M$. \medskip \emph{Step 2:} Partition $Q$ in indistinguishable states. \medskip \emph{Step 3:} Read off the minimal DFA. \end{construction} \pause\medskip \begin{block}{} \emph{Step 1:} Remove all unreachable states from $M$. \medskip Remove all states $q \in Q$ for which there is no path from $q_0$ to $q$. \end{block} \end{frame}