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

Problem Detail: 

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?

Asked By : saadtaame

Answered By : saadtaame

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_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 < j$, we can write $\alpha = x_1x_2\dots x_m$. $A \rightarrow X_1X_2\dots X_m$ is a production in $P$ and a derivation looks like: $A \rightarrow X_1X_2\dots X_m \rightarrow^* x_1X_2\dots X_m \rightarrow^* \dots \rightarrow^* x_1x2\dots 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_2\dots 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3250

 Ask a Question

 Download Related Notes/Documents