\begin{frame}{Applications}
  \begin{exampleblock}{}
    $L \setminus \{\, \lambda \,\}$ is context-free for every context-free language $L$.
  \end{exampleblock}
  \pause\medskip
  
  \begin{exampleblock}{}
    $\{\,a^n b^n \mid n \geq 1000\,\}$ is context-free.
  \end{exampleblock}
  \pause\medskip
    
  \begin{exampleblock}{}
    Show that the language
    \begin{talign}
      L = \{\, w\in\{a,b,c\}^*\mid n_a(w) = n_b(w) = n_c(w) \,\}
    \end{talign}
    is \emph{not} context-free.
    \pause\medskip
  
    For a contradiction, assume $L$ was context-free.
    \pause\medskip
    
    The language $L(a^*b^*c^*)$ is regular, thus
    \begin{talign}
      L \cap L(a^*b^*c^*) = \{\, a^n b^n c^n \mid n\geq 0 \,\}
    \end{talign}
    would be context-free. \pause
    However, we know that it is not.
    \pause\medskip
    
    Contradiction. Thus $L$ is not context-free.
  \end{exampleblock}
\end{frame}

\themex{Decidability}