4
$\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$
4
  • $\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$ Jan 1, 2016 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, 2016 at 17:24
  • $\begingroup$ But why isn't $m=n$ equal to the number of internal nodes in the derivation-tree? $\endgroup$ Jan 1, 2016 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, 2016 at 23:23

1 Answer 1

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$
6
  • $\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, 2016 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$ Jan 1, 2016 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, 2016 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, 2016 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$ Jan 1, 2016 at 15:06

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.