26/80
\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}