\begin{frame}{Basic Properties of Context-Free Languages}
  \begin{block}{Theorem}
    If $L_1$ is \alert{context-free} and $L_2$ \alert{regular}, then $L_1 \cap L_2$ is \alert{context-free}.
  \end{block}
  \pause

  \begin{construction}
    Let 
    \begin{itemize}
      \item $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ be an NPDA accepting $L_1$, and
      \item $N = (R,\Sigma,\epsilon,r_0,G)$ a DFA accepting $L_2$.
    \end{itemize} 
    \pause
    We construct an NPDA 
    $\widehat M=(\widehat Q,\alert{\Sigma},\alert{\Gamma},\widehat\delta,\widehat q_0,\alert{z},\widehat F)$ where
    \begin{talign}
      \alert{\widehat Q} = Q\times R \hspace*{1.5cm}
      \alert{\widehat q_0} = (q_0,r_0) \hspace*{1.5cm}
      \alert{\widehat F} = F\times G
    \end{talign}
    \pause
    The transition function $\alert{\widehat\delta}$ is defined by:
    \begin{itemize}
    \pause
      \item 
        \alert{$\widehat{M}$: $(q,r) \stackrel{a[b/v]}{\longrightarrow} (q',r')$}
        if $M$: $q \stackrel{a[b/v]}{\longrightarrow} q'$
        and $N$: $r \stackrel{a}{\longrightarrow} r'$
    \pause
      \item 
        \alert{$\widehat{M}$: $(q,r) \stackrel{\lambda[b/v]}{\longrightarrow} (q',r)$}
        if $M$: $q \stackrel{\lambda[b/v]}{\longrightarrow} q'$
        \smallskip
    \end{itemize}
    \pause
    Then \alert{$L(\widehat M)=L(M)\cap L(N)$}.
  \end{construction}
\end{frame}