context free – Formal proof of existence of equivalent parse tree for each derivation

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 an A-derivation tree $t_pi$ with
yield $alpha$ as follows.

  1. if $n = 0$, then $t_pi$ is the one-node tree such that $dom(t_{pi}) = { epsilon }$ and $t_{pi}(epsilon) = A$
  2. 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 associated with the
derivation $A stackrel{n-1}{implies} alpha$.

enter image description here
enter image description here