\begin{frame}{Regular Languages: Complement}
  \begin{block}{Theorem}
    If $L$ is a regular language, then \alert{$\overline{L}$} is also regular.
  \end{block}
  \pause
  \begin{proof}
    Let $L$ be regular. 
    \medskip\pause
    
    Then there exists a DFA $M = (Q,\Sigma,\delta,q_0,F)$ with $L(M) = L$.
    \medskip\pause
    
    Then $N = (Q,\Sigma,\delta,q_0,\alert{Q\setminus F})$ is a DFA with $L(N) = \overline{L}$.
    \bigskip\pause

    Here it is \alert{important} that for every input word $w$:
    \begin{itemize}
      \item There is precisely one path starting at $q_0$ labelled with $w$.
      \pause
      \item There is \alert{precisely one state $q$ with $q_0 \apath{w} q$}.
      \pause Thus
      \begin{talign}
        w &\in L \iff w \in L(M) \iff q \in F\\ 
        \mpause[1]{ w &\in \overline{L} \iff w \in \overline{L(M)} \iff q \in (Q\setminus F) \iff w \in L(N) }
      \end{talign}
    \end{itemize} 
  \end{proof}
\end{frame}