28/49
\begin{frame}{Derivation Trees}
\begin{block}{}
A \emph{derivation tree} for a context-free grammar $G=(V,T,S,P)$:
\begin{itemize}
\item
Nodes have labels from $V \cup T \cup \{\lambda\}$.
The \emph{root} has label $S$.

\item
A node with label $A \in V$ can have children labelled
\begin{itemize}
\item $x_1,\ldots,x_n$ if there is a rule $A \to x_1 \cdots x_n$ with $n\geq 1$, or
\item $\lambda$ (single child) if there is a rule $A \to \lambda$.
\end{itemize}

\item
Every node with a label from $T \cup \{\lambda\}$ is a \emph{leave}.
\end{itemize}
\end{block}

\begin{exampleblock}{}
In the grammar $S \to SaS \mid b$, a \emph{derivation tree} for $bab$ is:
\begin{center}
\begin{tikzpicture}[default,>=latex,l/.style={yshift=-7mm},node distance=10mm,thin,nodes={inner sep=0}]
\node (1) {$S$};
\node (2a) [left of=1,l] {$S$};
\node (2b) [at=(1),l] {$a$};
\node (2c) [right of=1,l] {$S$};
\node (3a) [at=(2a),l] {$b$};
\node (3c) [at=(2c),l] {$b$};

\draw (1) to (2a);
\draw (1) to (2b);
\draw (1) to (2c);
\draw (2a) to (3a);
\draw (2c) to (3c);
\end{tikzpicture}
\end{center}
\end{exampleblock}
\pause

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