# Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar

I am trying to prove the following theorem:

For every derivation-tree in a context-free grammar $G=(V,T,P,S)$ there exists at most one leftmost derivation.

My partial proof by contradiction (I stucked at Cases (2) and (3)):

Let $G = (V,T,P,S)$ be a context-free grammar.

Suppose that for some derivation-tree there are two distinct rightmost derivations:

$S = πΆ_0 βΉ_{lm} πΆ_1 βΉ_{lm} πΆ_2 βΉ_{lm} β¦ βΉ_{lm} πΆ_n = x$ $S = π·_0 βΉ_{lm} π·_1 βΉ_{lm} π·_2 βΉ_{lm} β¦ βΉ_{lm} π·_m = x$
(x is the frontier of the tree)

It is clear that $πΆ_1 = π·_1$ since the first derivation uses a production rule of the form $S βΆ Y_1 β¦ Y_k$ where $Y_1 β¦ Y_k$ are the children of the root node $S$.

Now since the derivations are distinct we get that there are three cases:

(1) $β i_0 β \{2, β¦ , min(m, n)\}, (β k β \{ 0, β¦ , i0 -1 \}, πΆ_k = π·_k ) β πΆ_{i_0} β π·_{i_0}$
(In other words: it says that the two derivations are identical till we reach some point in both derivations where they become distinct)

(2) $n < m β β k β \{ 0, β¦ , n \}, πΆ_k = π·_k$
(In other words: it says that the first derivation is a βsubβ derivation of the second one)

(3) $n > m β β k β \{ 0, β¦ , m \}, πΆ_k = π·_k$
(In other words: it says that the second derivation is a βsubβ derivation of the first one)

Case (1): If $β i0 β \{2, β¦ , min(m, n)\}, (β k β \{ 0, β¦ , i0 -1 \}, πΆ_k = π·_k ) β πΆ_{i_0} β π·_{i_0}$ , We get that $βwβT^*, π·β(VβͺT)^* , AβV, πΆ_{i_0-1} = π·_{i_0-1} = wAπ·$ , Since both derivations are in the same derivation-tree, The only possibility is that different production rules where used on different variables, but since the derivations are leftmost-derivations, we must use at the $i_0$βth derivation the corresponding production-rule (in the derivation-tree) on $A$, since $A$ is the leftmost variable. Again, since the derivations are in the same derivation-tree, The production rule used on A must be the same rule $A βΆ Z_1 β¦ Z_k$ where $Z_1 β¦ Z_k$ are the children nodes of the node $A$. Therefore we reached the contradiction $πΆ_{i_0} = π·_{i_0}$.

Case (2): If $n < m β β k β \{ 0, β¦ , n \}, πΆ_k = π·_k$ then we get that $πΆ_n = π·_n$ , Now since $πΆ_n = x$ we get $πΆ_n = π·_n = x$, Since m > n and since $x = π·_n βΉ_{lm} β¦ βΉ_{lm} π·_m = x$, we get that $x βΉ_{lm}^+ x$.

Now I do not know how to proceed.

Case (3): If $n > m β β k β \{ 0, β¦ , m \}, πΆ_k = π·_k$ then we get that $πΆ_m = π·_m$ , Now since $πΆ_m = x$ we get $πΆ_m = π·_m = x$, Since n > m and since $x = πΆ_m βΉ_{lm} β¦ βΉ_{lm} πΆ_n = x$, we get that $x βΉ_{lm}^+ x$.

Now I do not know how to proceed.

Maybe it got something to do with the fact that $x$ is the frontier of the derivation tree.

Thanks for any help.

• Sorry, but I am having a difficulty in understanding why you need contradiction and all that. Isn't it enough to conclude that in any moment there is at most one leftmost nonterminal? Commented Jan 1, 2016 at 16:43
• @HendrikJan My university textbook shows this proof, but only for the case (1), I have noticed that there are additional two cases (cases (2) and (3)) that weren't mentioned in the textbook's proof and I got stucked at proving those two cases. Commented Jan 1, 2016 at 17:24
• But why isn't $m=n$ equal to the number of internal nodes in the derivation-tree? Commented Jan 1, 2016 at 21:25
• @HendrikJan Thanks a lot. I haven't took this observation into account, Thus cases (2) and (3) never come up. Commented Jan 1, 2016 at 23:23

Here is a paraphrase of your proof. Suppose $$S \Rightarrow \alpha_1 \Rightarrow \cdots \Rightarrow \alpha_n \Rightarrow w \\ T \Rightarrow \beta_1 \Rightarrow \cdots \Rightarrow \beta_m \Rightarrow w$$ are two leftmost derivations corresponding to the same derivation tree. Then the first step must be the same. This is the point where you're stuck.

What you want to do now is to say that $\alpha_1 \Rightarrow \cdots \Rightarrow w$ and $\beta_1 \Rightarrow \cdots \Rightarrow w$ are also leftmost derivations corresponding to the same derivation tree (obtained from the original one by taking into account the first step), and so by induction these derivations are the same.

There is a small problem β $\alpha_1$ is now not a single symbol! You therefore have to strengthen your induction hypothesis and prove something more general which involves derivation trees starting from sentential forms (words which can involve both terminals and non-terminals).

Alternatively, if you prefer using frontiers of derivation trees, you should strengthen your induction hypothesis in a different (but equivalent) way. Now you are still given the original derivation tree, but some of the productions are marked as already having been performed. Your induction hypothesis now states that all leftmost derivations from this state are the same.

It's also possible to avoid strengthening the induction hypothesis, at the cost of a more complicated argument during the inductive step. Suppose that the first step is $S \to x_1 A_1 x_2 A_2 \dots x_n A_n x_{n+1}$, where $A_1,\ldots,A_n$ are non-terminals and $x_1,\ldots,x_{n+1}$ are words. Any leftmost derivation must first completely derive $A_1$, then completely derive $A_2$, and so on, until $A_n$ is completely derived. Induction shows that there is only one way to achieve any of these $n$ steps.

More generally, I suppose you focus first on why the result is true; only then focus on how to write the argument formally.

• So you mean that I need to prove by induction on the height of the derivation tree that any two leftmost derivation sequences (in the tree) are identical? Commented Jan 1, 2016 at 13:13
• That's the statement of your problem. For an inductive proof to work you probably need to prove a stronger claim by induction. Commented Jan 1, 2016 at 13:18
• So I need to prove by induction on the height of a derivation tree that starts with a sentential form that any two leftmost derivation sequences (in the tree) are identical. I think I got it. Commented Jan 1, 2016 at 13:24
• Can you help me a little in the inductive step. I supposed that for any derivation tree of height $n$ that starts with a sentential form, any two leftmost derivation sequences in the tree are identical. Now I try to prove that for any derivation tree of height $n+1$ that starts with a sentential form, any two leftmost derivation sequences are identical. But I got stuck. I do not really get how to apply the induction hypothesis on the new tree. Commented Jan 1, 2016 at 14:02
• I'm not sure you want to do induction on the height. Perhaps on the number of edges. Give it a few days β the only way to understand induction is by solving such exercises on your own. Commented Jan 1, 2016 at 15:06