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

Question

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.

Answer 1

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.