# Formal proof of existence of equivalent parse tree for each derivation

Where I can find formal proof of there exists an equivalent parse tree for each derivation? There is a lot of informal proof of equivalency on the internet but I need formal proof to reference it in a paper.

• There is no need to reference such a trivial fact in a paper. Sep 12 at 8:53
• @YuvalFilmus can you please direct me to formal proof? Sep 12 at 16:47
• You can take look at any decent textbook. Sep 12 at 17:09

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