\begin{frame}{Minimal DFAs (3)}
  \begin{block}{}
    \emph{Step 3:} Read off the minimal DFA.
    \pause\medskip
    
    Let $Q_1,\ldots,Q_n$ be the final partition of $Q$.
    \pause\medskip
    
    These are the \alert{states} of the minimal DFA $\widehat M$.
    \pause\medskip
    
    The \alert{transitions} (arrows) of $\widehat M$ are:
    \begin{talign}
      Q_i \stackrel{a}{\to} Q_j \quad\iff\quad q \stackrel{a}{\to} q' \mbox{ for some $q \in Q_i$, $q' \in Q_j$} % \delta(q,a) \in Q_j \mbox{ for some } q \in Q_i
    \end{talign}
    \pause
    The \alert{starting state} is the set that contains $q_0$.
    \pause\medskip
    
    The \alert{final states} are the subsets of $F$.
  \end{block}
  \pause\medskip
  
  \begin{goal}{}
    \structure{Worst-case time complexity}: $O(|\Sigma|{\cdot}|Q|^2)$, since
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item There are maximal $|Q|-1$ splits.
      \item Every split costs maximal $O(|\Sigma|{\cdot}|Q|)$.
    \end{itemize}
  \end{goal}
\end{frame}