\begin{frame}{Elementary Properties of Regular Languages}
  \begin{goal}{Theorem}
    If $L_1$, $L_2$, $L$ are regular languages, then also 
    \begin{talign}
      L_1 \cup L_2
      && L_1 \cap L_2
      && L_1 L_2
      && \overline{L}
      && L_1 \backslash L_2
      && L^*
      && L^R
    \end{talign}
  \end{goal}
  \pause
  
  \begin{proof}
    Let $r_1,r_2,r$ be regular expr. with $L(r_1) = L_1$, $L(r_2) = L_2$, $L(r) = L$.%
    \begin{itemize}\setlength{\itemsep}{-.3ex}
    \pause
    \item
      $L_1 \cup L_2 = \pause \alert{L(r_1 + r_2)}$ is regular.
    \pause
    \item
      $L_1 L_2 = \pause \alert{L(r_1 \cdot r_2)}$ is regular.
    \pause
    \item
      $L^* = \pause \alert{L(r^*)}$ is regular.
    \pause
    \item
      $L$ is accepted by some DFA $(Q,\Sigma,\delta,q_0,F)$.
      
      $\overline{L} = \alert{L((Q,\Sigma,\delta,q_0,Q\backslash F))}$ is regular.
    \pause
    \item
      $L_1 \cap L_2 \pause = \alert{\overline{\overline{L_1} \cup \overline{L_2}}}$ is regular. \qedhere
    \pause
    \item
      $L_1 \backslash L_2 \pause = \alert{L_1 \cap \overline{L_2}}$ is regular.
    \pause
    \item 
      For $L^R$, take an NFA that accepts $L$. 
      Reverse all arrows.
      Swap final and starting states. The result accepts $L^R$.
    \end{itemize}
  \end{proof}
\end{frame}