\begin{frame}{Equality of Context-Free Languages}
    The question \alert{$L = \Sigma^*$ ?} (and hence \alert{$L_1 = L_2$ ?}) for context-free languages $L$ ($L_1,L_2$) is undecidable.
    Given a PCP $X$: \alert{$(w_1,v_1),\ldots,(w_n,v_n)$}.
    Define $G_1$ and $G_2$:
      \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}
    as before. \pause
      \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^*}}
    It suffices to show that $\overline{L(G_1)} \cup \overline{L(G_2)}$ is context-free.
    It suffices that $\overline{L(G_1)}$ is context-free ($\overline{L(G_2)}$ is analogous).