\begin{frame}{Equality of Context-Free Languages}
  \begin{goal}{Theorem}
    The question \alert{$L = \Sigma^*$ ?} (and hence \alert{$L_1 = L_2$ ?}) for context-free languages $L$ ($L_1,L_2$) is undecidable.
  \end{goal}
  \pause
  
  \begin{block}{Proof}
    Given a PCP $X$: \alert{$(w_1,v_1),\ldots,(w_n,v_n)$}.
    \pause
    Define $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}
    as before. \pause
    Then
    \begin{talign}
      \text{PCP $X$ has no solution} 
      &\iff L(G_1) \cap L(G_2) = \emptyset  \\
      \mpause[1]{&\iff \overline{L(G_1) \cap L(G_2)} = \overline{\emptyset}} \\
      \mpause{&\iff \alert{\overline{L(G_1)} \cup \overline{L(G_2)} = \Sigma^*}}
    \end{talign}
    \pause\pause\pause
    It suffices to show that $\overline{L(G_1)} \cup \overline{L(G_2)}$ is context-free.
    \pause\medskip
    
    It suffices that $\overline{L(G_1)}$ is context-free ($\overline{L(G_2)}$ is analogous).
  \end{block}
\end{frame}