\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}