Proposition 6.11

*Full manuscript*: https://www.cis.upenn.edu/~jean/gbooks/tocnotes.html

Definition 3.11.2: Given a context-free grammar $G = (V, Sigma, P,

> S)$, for any $A in N$, if $pi: A stackrel{n}{implies} alpha$ is a

derivation in $G$, we construct anA-derivation tree$t_pi$ with

yield $alpha$ as follows.

- if $n = 0$, then $t_pi$ is the one-node tree such that $dom(t_{pi}) = { epsilon }$ and $t_{pi}(epsilon) = A$
- if $A stackrel{n-1}{implies} lambda B rho$ and if $t_1$ is the A-derivation tree with yield $lambda B rho$ associated with the

derivation $A stackrel{n-1}{implies} lambda B rho$, and if $t_2$

is the tree associated with the production $B rightarrow gamma$

that is, if $gamma = X_1 dots X_n$,then $dom(t_2) = { epsilon, 1, dots, k }$, $t_2(epsilon) = B$,

and $t_2(i) = X_i$ or all $i$, $1 leq i leq k$, of if $gamma = epsilon$then $dom(t_2) = { epsilon, 1 }$, $t_2(epsilon) = B$, and $t_2(1) = epsilon$,

then $t_{pi} = t_1(u gets t_2)$, where $u$ is the address of the

leaf labeled $B$ in $t_1$.The tree $t_{pi}$ is the

A-derivation tree associatedwith the

derivation $A stackrel{n-1}{implies} alpha$.