\begin{frame}{Palindromes in Context-Free Languages}
  \begin{goal}{Theorem}
    It is undecidable whether a context-free languages contains a palindrome
    (a word $w = w^R$).
  \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 a context-free grammar $G$:
    \begin{talign}
      \alert{S \to w_i \,S\, v_i^R \mid w_i \,\#\,v_i^R}
    \end{talign}
    for $1 \le i \le n$. Here $\#$ is a fresh symbol.
    \pause\medskip
    
    $L(G)$ contains a palindrome \;$\iff$\; PCP $X$ has a solution.
  \end{proof}
\end{frame}