\begin{frame}{Grammar Derivations}
  \begin{block}{}
    If $x \to y$ is a production rule, then we have a \emph{derivation step}
    \begin{talign}
      uxv \Rightarrow uyv
    \end{talign}
    for every $u,v \in (V \cup T)^*$.
  \end{block}
  \pause
  
  \begin{exampleblock}{}
    $G = (\{S\}, \{a,b\}, S, P)$, where $P$ consists of
    \begin{talign}
      S &\to aSb &
      S &\to \lambda
    \end{talign}    
    \pause\vspace{-6mm}
    
    Example derivations:
    \begin{talign}
      \mpause[1]{S} \mpause{&\Rightarrow \lambda} & \mpause[11]{S &\Rightarrow^* \lambda} \\
      \mpause[3]{S} \mpause{&\Rightarrow aSb} \mpause{\Rightarrow ab} & \mpause[11]{S &\Rightarrow^* ab} \\
      \mpause[6]{S} \mpause{&\Rightarrow aSb} \mpause{\Rightarrow aaSbb} \mpause{\Rightarrow aabb} & \mpause[11]{S &\Rightarrow^* aabb}
    \end{talign}\vspace{-2ex}
  \end{exampleblock}
  \pause[13]
    
  \begin{goal}{}
    A \emph{derivation} $\Rightarrow^*$ is the reflexive, transitive closure of $\Rightarrow$.
  \end{goal}
  Thus there is a derivation 
  $u \Rightarrow^* v$
  if $v$ can be obtained from $u$ by zero or more derivation steps.
\end{frame}