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}