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