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

    Here it is \alert{important} that for every input word $w$:
      \item There is precisely one path starting at $q_0$ labelled with $w$.
      \item There is \alert{precisely one state $q$ with $q_0 \apath{w} q$}.
      \pause Thus
        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) }