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