\begin{frame}{Equality of Context-Free Languages (3)}
  \begin{block}{Proof continued}
    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}
    We distinguish three cases:\pause
    \begin{talign}
      L_S \setminus L(G_1) = \alert{L_\text{smaller} \cup L_\text{larger} \cup L_\text{equal}}
    \end{talign}
    where
    \begin{talign}
      L_\text{smaller} &= \{ w \;\#\; \langle k \rangle \cdots \langle j \rangle \;\mid\; |w| < |w_j \cdots w_k| \} \\
      L_\text{larger} &= \{ w \;\#\; \langle k \rangle \cdots \langle j \rangle \;\mid\; |w| > |w_j \cdots w_k| \} \\
      L_\text{equal} &= \{ w \;\#\; \langle k \rangle \cdots \langle j \rangle \;\mid\; |w| = |w_j \cdots w_k| \;\&\; w \ne w_j \ldots w_k\}
    \end{talign}
    \pause
    Each of these languages is context-free, thus $L_S \setminus L(G_1)$ is.
  \end{block}
  \pause\medskip
  
  \begin{exampleblock}{Exercise}
    Give context-free grammars for $L_\text{smaller}$, $L_\text{larger}$ and $L_\text{equal}$.
  \end{exampleblock}
  \vspace{10cm}
\end{frame}

\themex{Semidecidability}