\begin{frame}{Removal of Useless Variables}
  \begin{question}
  How to determine useless variables of a context-free grammar?
  \end{question}
  \pause
  
  \begin{construction}
    %     Let $G$ be a context-free grammar.
    %     \pause\medskip
    %     
    A variable $A$ is called \emph{productive} if 
    $A \Rightarrow^+ w$ with $w \in T^*$.
    \pause\medskip
    
    We determine all productive variables:
    \begin{itemize}
      \item If $A \to y$ is a rule and all variables in $y$ are productive,\\ then $A$ is productive.
    \end{itemize}
    \pause

    Remove all rules that contain a \alert{non-}productive variable.    
    \pause\medskip

    We determine all \emph{reachable} variables as follows:
    \begin{itemize}
      \item $S$ is reachable.
      \item If $A \to y$ and $A$ is reachable, then so are all variables in $y$.
    \end{itemize}
    \pause
    Remove all rules that contain a \alert{non-}reachable variable.    
    \pause\medskip

    A variable is \alert{useless} if it is \alert{not in one of the remaining rules}.
  \end{construction}
  \bigskip
\end{frame}