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