\begin{frame}{Derivation Trees}
    A \emph{derivation tree} for a context-free grammar $G=(V,T,S,P)$:
      Nodes have labels from $V \cup T \cup \{\lambda\}$.
      The \emph{root} has label $S$.
      A node with label $A \in V$ can have children labelled 
        \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$.
      Every node with a label from $T \cup \{\lambda\}$ is a \emph{leave}.
    In the grammar $S \to SaS \mid b$, a \emph{derivation tree} for $bab$ is:
      \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);
    The labels of the leaves of a derivation tree, 
    read from left to right (skipping $\lambda$),
    form a word in $L(G)$.