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