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