45/103
\begin{frame}{Basic Properties of Context-Free Languages}
\begin{block}{Theorem}
If $L_1$ and $L_2$ are context-free,
then also
\begin{talign}
L_1 \cup L_2
&& L_1^R
&& L_1 L_2
&& L_1^*
\end{talign}
\end{block}
\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^R$}:
\pause
Reverse all right-hand sides ($x \to y$ becomes $x \to y^R$).
\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.
\end{itemize}
\end{proof}
\end{frame}