2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Hendrik Jan Jan 1 '16 at 16:43
  • $\begingroup$ @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. $\endgroup$ – MathNerd Jan 1 '16 at 17:24
  • $\begingroup$ But why isn't $m=n$ equal to the number of internal nodes in the derivation-tree? $\endgroup$ – Hendrik Jan Jan 1 '16 at 21:25
  • $\begingroup$ @HendrikJan Thanks a lot. I haven't took this observation into account, Thus cases (2) and (3) never come up. $\endgroup$ – MathNerd Jan 1 '16 at 23:23
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – MathNerd Jan 1 '16 at 13:13
  • 1
    $\begingroup$ That's the statement of your problem. For an inductive proof to work you probably need to prove a stronger claim by induction. $\endgroup$ – Yuval Filmus Jan 1 '16 at 13:18
  • $\begingroup$ 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. $\endgroup$ – MathNerd Jan 1 '16 at 13:24
  • $\begingroup$ 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. $\endgroup$ – MathNerd Jan 1 '16 at 14:02
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 1 '16 at 15:06

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.