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}