\begin{frame}{Equality of Context-Free Languages (2)} \begin{block}{Proof continued} \vspace{-1ex} \begin{talign} S_1 &\rightarrow w_i S_1 \langle i \rangle \mid w_i \,\#\, \langle i \rangle \end{talign} The words in $L(G_1)$ are of the form \begin{salign} w_j \cdots w_k \;\#\; \langle k \rangle \cdots \langle j \rangle \quad \text{ for non-empty indices $1 \le j,\ldots,k \le n$} \end{salign} All these words are of the shape \begin{salign} \alert{L_S = \Sigma^* \cdot \{\, \# \,\} \cdot \{\, \langle 1 \rangle,\ldots,\langle n \rangle \,\}^+}. \end{salign} \pause We have $L(G_1) \subseteq L_S$, so \begin{salign} \alert{\overline{L(G_1)}} = \Sigma^* \setminus L(G_1) = (L_S \cup \overline{L_S}) \setminus L(G_1) = \alert{(L_S \setminus L(G_1)) \cup \overline{L_S}} \end{salign} \pause As $L_S$ is regular, also $\overline{L_S}$ is regular (and context-free). \pause\medskip So it suffices to show that \alert{$L_S \setminus L(G_1)$} is context-free. \pause\medskip The words in $L_S \setminus L(G_1)$ are of the form: \begin{salign} \alert{L_S \setminus L(G_1) = \{\, w \;\#\; \langle k \rangle \cdots \langle j \rangle \;\mid\; w \ne w_j \cdots w_k\,\}} \end{salign} \pause We distinguish three cases\ldots \end{block} \vspace{10cm} \end{frame}