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.

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

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.