Proof of equivalence of parse-trees and derivations

Intuitively, every derivation in a context-free grammar corresponds to a parse-tree and vise versa.

Is this intuition correct? If so how can I formalize and prove such a thing?

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:

• $V$ is the set of non-terminals

• $T$ is the set of terminals

• $P$ is the set of productions

• $S \in V$ is a designated start symbol.

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

• The root is labeled with a symbol $\in V$

• 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_2\dots X_n$ is a production $\in P$.

proof. We prove $\forall A \in V, A \rightarrow^ \alpha \Rightarrow\exists$ 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

• Add a link between $A$ and every node labeled with a symbol $\in V'$

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

StackExchange Computer Science Q#3250, answer score: 3