\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}