23/46
\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}
\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}