\begin{frame}{Grammar Derivations}
    If $x \to y$ is a production rule, then we have a \emph{derivation step}
      uxv \Rightarrow uyv
    for every $u,v \in (V \cup T)^*$.
    $G = (\{S\}, \{a,b\}, S, P)$, where $P$ consists of
      S &\to aSb &
      S &\to \lambda
    Example derivations:
      \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}
    A \emph{derivation} $\Rightarrow^*$ is the reflexive, transitive closure of $\Rightarrow$.
  Thus there is a derivation 
  $u \Rightarrow^* v$
  if $v$ can be obtained from $u$ by zero or more derivation steps.