71/122
\begin{frame}{Regular Languages: Intersection, Difference}
\begin{exampleblock}{Question}
Change the product construction to show that
\begin{itemize}
\item $L_1 \cap L_2$ is regular, and
\item $L_1 \setminus L_2$ is regular ?
\end{itemize}
\pause\smallskip

\emph{Answer:} it suffices to change the definition of the final states
\begin{itemize}
\item
for $L_1 \cup L_2$: $F = \{\, (q_1,q_2) \in Q \mid q_1 \in F_1 \text{ or } q_2 \in F_2 \,\}$
\pause
\item
for $L_1 \cap L_2$: $F =\pause \{\, (q_1,q_2) \in Q \mid q_1 \in F_1 \text{ \alert{and} } q_2 \in F_2 \,\}$
\pause
\item
for $L_1 \setminus L_2$:\, $F =\pause \{\, (q_1,q_2) \in Q \mid q_1 \in F_1 \text{ \alert{and} } q_2 \alert{\not\in} F_2 \,\}$
\end{itemize}
\end{exampleblock}
\pause

\begin{block}{Theorem}
If $L_1$ and $L_2$ are regular, then \alert{$L_1 \cap L_2$} is regular.
\end{block}
\pause

\begin{block}{Theorem}
If $L_1$ and $L_2$ are regular, then \alert{$L_1 \setminus L_2$} is regular.
\end{block}

%   \begin{block}{Theorem}
%     If $L$ is regular, then \alert{$L^R$} is also regular.
%   \end{block}
\end{frame}