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