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