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?

  • $\begingroup$ Did you check the proof yourself? Is there a particular part you are doubtful of? Inductions are certainly a good idea; no time right now to digest the details. (Note that questions which have boring "Yes" (or "No") answers are not very good for this platform.) $\endgroup$ – Raphael Aug 18 '12 at 17:23
  • 3
    $\begingroup$ Definitely not! We welcome questions of all CS flavors and levels. We don't welcome the usual kinds of questions that are bad for SE, even if they are CS questions, as well as pure programming questions. Yours is not bad per se: you show clear effort and there is a correct answer. All I'm saying is that your "question" -- "check my proof" -- is boring, not to mention time consuming. If you can focus your question or make it otherwise more appealing, you stand a better chance of receiving an answer. $\endgroup$ – Raphael Aug 18 '12 at 18:40
  • 1
    $\begingroup$ I don't know what you mean by that. Generally, we don't like lists much. SE is a Q&A platform, after all; a wiki works much better for such collections. $\endgroup$ – Raphael Aug 18 '12 at 20:43
  • 1
    $\begingroup$ This question should be closed. Alternatively, @saadtaame can edit the question to have the theorem, and copy the proof into an answer. $\endgroup$ – Ran G. Oct 1 '12 at 17:57
  • 1
    $\begingroup$ with your permission, I slightly edited the question to make it a question.. (: Thanks for revising it according to the comments. $\endgroup$ – Ran G. Oct 1 '12 at 19:00

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$

Fig. 1 Parse-tree for the base case

This ends the proof.

  • $\begingroup$ Posting answers to your own questions has the connotation of "this is correct". Are you certain it is by now? $\endgroup$ – Raphael Oct 2 '12 at 17:41
  • $\begingroup$ @Raphael Yes I am. $\endgroup$ – mrk Oct 2 '12 at 20:19

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.