103/123
\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}