[Solved]: Proof of equivalence of parse-trees and derivations

Theorem. Let $G = (V, T, P, S)$ be a Context-free Grammar. Then $forall A in V, A rightarrow^* alpha Leftrightarrow exists$ a parse-tree $T’$ rooted at node $A$ with yield $alpha in (V cup T)^*$. Meanings of symbols:

1. $V$ is the set of non-terminals
2. $T$ is the set of terminals
3. $P$ is the set of productions
4. $S in V$ is a designated start symbol.

A parse-tree $T’$ for a derivation is defined as follows:

1. The root is labeled with a symbol $in V$
2. If $T’$ has a node labeled $A$ whose children are labeled $X_1, X_2, dots, X_n$ such that $X_i$ is to the left of $X_j$ for all $i lt j$, then $A rightarrow X_1X_2dots X_n$ is a production $in P$.

proof. We prove $forall A in V, A rightarrow^* alpha Rightarrowexists$ a parse-tree $T’$ rooted at $A$ with yield $alpha in (V cup T)^*$ and vice-versa. We will refer to a node with label $L$ as node $L$. First we show the ($Leftarrow$) part. Assume there is a parse-tree $T’$ rooted at $A$ with yield $alpha$. If the tree has $1$ internal node, then $A rightarrow alpha$ is a production in $P$ (by definition of a parse-tree). Since $A rightarrow alpha Rightarrow A rightarrow^* alpha$, we are done. Assume that the ($Leftarrow$) part holds for all parse-trees with fewer than $n$ internal nodes (induction hypothesis). If the parse-tree has $n gt 1$ internal nodes, let $X_i, i = 1, 2, dots, m$ (be it a non-terminal or a terminal) denote the label of the $i^{th}$ child of the root-node $A$. Each of the $X_i$ nodes has fewer than $n$ nodes. By the induction hypothesis, each of the $X_i$ nodes is the root of a parse-tree with yield $x_i$. Knowing that all the descendants of $X_i$ are to the left of all of the descendants of $X_j$ for all $i < j$, we can write $alpha = x_1x_2dots x_m$. $A rightarrow X_1X_2dots X_m$ is a production in $P$ and a derivation looks like: $A rightarrow X_1X_2dots X_m rightarrow^* x_1X_2dots X_m rightarrow^* dots rightarrow^* x_1x2dots x_m = alpha$. Now we show the ($Rightarrow$) part. Assume $A rightarrow^* alpha$ for some $A in V$. If $A rightarrow alpha$, then the tree in Fig. 1 is a parse-tree with yield $alpha$ and we are done. Assume that the ($Rightarrow$) part holds for all derivations with fewer than $n$ steps (induction hypothesis). If $A rightarrow^* alpha$ is a derivation with $n$ steps, let $A rightarrow X_1X_2dots X_n$ be the first step in the derivation-chain. Let $V’ = {X_1, X_2, dots, X_n} cap V$. Each of the elements of $V’$ derives a sub-string of $alpha$ with fewer than $n$ steps. By the induction hypothesis, there is a parse-tree rooted at node $V’_i$ with yield $v’_i$. We form a parse tree rooted at $A$ with yield $alpha$ as follows:

1. Add a root-node labeled with $A$
2. Add a link between $A$ and every node labeled with a symbol $in V’$
3. Add a link between $A$ and every node labeled with a symbol $in {X_1, X_2, dots, X_n} cap T$

This ends the proof.