17/35
\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}