\begin{frame}{Empty Intersection of Context-Free Languages}
  \begin{goal}{Theorem}
    The question \alert{$L_1 \cap L_2 = \emptyset$ ?} for context-free languages $L_1$, $L_2$
    is undecidable.
  \end{goal}
  \pause
  
  \begin{proof}
    We reduce the PCP to the above problem.
    \pause\medskip
        
    Given a PCP instance $X$: \alert{$(w_1,v_1),\ldots,(w_n,v_n)$}.
    \pause\medskip
        
    We define two context-free grammars $G_1$ and $G_2$:
    \begin{talign}
      \alert{S_1} &\alert{\rightarrow w_i S_1 \langle i \rangle \mid w_i \,\#\, \langle i \rangle} \\ 
      \alert{S_2} &\alert{\rightarrow v_i\, S_2 \langle i \rangle \mid v_i\, \,\#\, \langle i \rangle}
    \end{talign}
    for $1 \le i \le n$. Here $\#$, $\langle$ and $\rangle$ are fresh symbols. \pause Then
    \begin{talign}
      L(G_1) &= \{w_j \cdots w_k \;\#\; \langle k \rangle \cdots \langle j \rangle \mid 1 \le j,\ldots,k \le n\} \\
      L(G_2) &= \{v_\ell \cdots v_m \;\#\; \langle m \rangle \cdots \langle \ell \rangle \mid 1 \le \ell,\ldots,m \le n\}
    \end{talign}
    \pause
    $L(G_1)\cap L(G_2)=\emptyset$ \;$\iff$\; the PCP $X$ has no solution.
  \end{proof}
\end{frame}