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