patternMinor
Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar
Viewed 0 times
provingfreederivationeveryhasonethatgrammarcontextleftmost
Problem
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, … , 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 n and since $x = _n ⟹_{lm} … ⟹_{lm} _m = x$, we get that $x ⟹_{lm}^+ x$.
Now I do not know how to proceed.
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, … , 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 n and since $x = _n ⟹_{lm} … ⟹_{lm} _m = x$, we get that $x ⟹_{lm}^+ x$.
Now I do not know how to proceed.
Solution
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.
$$
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.
Context
StackExchange Computer Science Q#51347, answer score: 3
Revisions (0)
No revisions yet.