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