14/216
\begin{frame}{Derivation Trees}
\begin{block}{}
A \emph{derivation tree} for a context-free grammar $G=(V,T,S,P)$
has nodes with labels from $V \cup T \cup \{\lambda\}$.

\begin{itemize}
\item
The \emph{root} has the label $S$.

\item
If there is a production rule
\begin{itemize}
\item $A \to x_1 \cdots x_n$ with $n\geq 1$, then\\
a node labelled $A$
can have children labelled $x_1,\ldots,x_n$.
\item $A \to \lambda$, then\\
a node labelled $A$
can have one child with label $\lambda$.
\end{itemize}

\item
Every node with a label from $T \cup \{\lambda\}$ is a \emph{leave}.\\
(That is, the node has no children).
\end{itemize}
\end{block}
\pause\medskip

\begin{goal}{}
The labels of the leaves of a derivation tree,
read from left to right (skipping $\lambda$),
form a word in $L(G)$.
\end{goal}
\end{frame}