\begin{frame}{Rightmost and Leftmost}
  
  Let $G$ be a grammar, and consider a derivation \alert{$S\Rightarrow^* w$}.
  \smallskip
  
  \begin{itemize}
    \item If $G$ is \emph{(right) linear}, $w$ contains \emph{at most one variable}.
    \item If $G$ is \emph{context-free}, $w$ can contain \emph{multiple variables}.
  \end{itemize}
  \pause\smallskip
  
  \begin{block}{}
    Two strategies to choose which variable to expand:
    \begin{itemize}
      \item \emph{leftmost}: always the leftmost variable
      \item \emph{rightmost}: always the rightmost variable
    \end{itemize} 
  \end{block}
  
  \begin{exampleblock}{}
    \begin{talign}
    S \to SaS \mid b
    \end{talign}

    Two derivations of $bab$:
    \smallskip
    
    \begin{tabular}{rl}
      \hspace{1cm}\emph{leftmost}: & $S \Rightarrow SaS \Rightarrow baS \Rightarrow bab$\\
      \emph{rightmost}: & $S \Rightarrow SaS \Rightarrow Sab \Rightarrow bab$
    \end{tabular}
  \end{exampleblock}
  \pause
  \begin{goal}{}
    Result depends not on the strategy, but the choice of the rules.
  \end{goal}
  \vspace{10cm}
\end{frame}