\begin{frame}{Basic Properties of Context-Free Languages}
  \begin{goal}{Theorem}
    If $L_1$ and $L_2$ are context-free,
    then also 
    \begin{talign}
      L_1 \cup L_2 
      && L_1 L_2
      && L_1^*
      && L_1^R 
    \end{talign}
  \end{goal}
  \pause
  
  \begin{proof}
    Let $G_i$ be a context-free grammar with start variable $S_i$ s.t.
    \begin{talign}
      L_i = L(G_i)
    \end{talign} 
    for $i=1,2$. \pause Let $G_1$ and $G_2$ have no variables in common.

    \begin{itemize}
    \pause
      \item 
        \alert{$L_1 \cup L_2$}:
        \pause
        Add rules $S \to S_1 \mid S_2$, and pick $S$ as start variable.
    \pause
      \item
        \alert{$L_1 L_2$}:
        \pause
        Add $S \to S_1 S_2$, and pick $S$ as start variable.
    \pause
      \item
        \alert{$L_1^*$}:
        \pause
        Add $S \to S_1S \mid \lambda$, and pick $S$ as start variable.
    \pause
      \item
        \alert{$L_1^R$}:
        \pause
        Reverse all rules ($x \to y$ becomes $x^R \to y^R$).
    \end{itemize}
  \end{proof}
\end{frame}