\begin{frame}{Rightmost and Leftmost}
  Let $G$ be a grammar, and consider a derivation \alert{$S\Rightarrow^* w$}.
    \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}.
    Two strategies to choose which variable to expand:
      \item \emph{leftmost}: always the leftmost variable
      \item \emph{rightmost}: always the rightmost variable
    S \to SaS \mid b

    Two derivations of $bab$:
      \hspace{1cm}\emph{leftmost}: & $S \Rightarrow SaS \Rightarrow baS \Rightarrow bab$\\
      \emph{rightmost}: & $S \Rightarrow SaS \Rightarrow Sab \Rightarrow bab$
    Result depends not on the strategy, but the choice of the rules.