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$– Yuval FilmusSep 12, 2021 at 8:53
-
$\begingroup$ @YuvalFilmus can you please direct me to formal proof? $\endgroup$– Node.JSSep 12, 2021 at 16:47
-
$\begingroup$ You can take look at any decent textbook. $\endgroup$– Yuval FilmusSep 12, 2021 at 17:09
1 Answer
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.
- 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 associated with the derivation $A \stackrel{n-1}{\implies} \alpha$.
-
1$\begingroup$ "Hyperlink-only" posts are frowned upon, for one thing, links may become stale. When possible to do so without IP violation, quote the essential part. $\endgroup$ Sep 13, 2021 at 0:02