\begin{frame}{Removal of Useless Variables}
  \begin{block}{}
    A variable $A$ is \emph{useless} for a context-free grammar 
    if there exists \alert{no} derivation of the form 
    \begin{talign}
      S \; \Rightarrow^* \; uAv \; \Rightarrow^+ \; w \quad\quad \text{with $w \in T^*$.}
    \end{talign}
  \end{block}  
  \pause
   
  \begin{goal}{}
    Removing production rules that contain a useless variable from a grammar 
    does not change the generated language.
  \end{goal}
  \pause
  
  \begin{exampleblock}{}
    \vspace{-1ex}
    \begin{talign}
      S &\to aSb \mid BC \mid \lambda &
      A &\to Sb &
      B &\to a &
      C &\to C
    \end{talign}
    Which variables are useless?
    \begin{itemize}
    \pause
      \item $A$ because there is no derivation $S \Rightarrow^* uAv$
    \pause
      \item $C$ because there is no derivation $C \Rightarrow^* w$ with $w \in T^*$
    \pause
      \item $B$ because $B$ can be reached only together with $C$
    \end{itemize}
    \pause
    The resulting grammar is \alert{$S \to aSb \mid \lambda$}.
  \end{exampleblock}
\end{frame}