# 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$$.