\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}