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