Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

Question

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof.

I've tried to prove it myself but I got stuck at the Inductive Step.

---

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

Prove by induction on $n$ where $n\geq 1$ that:

For every $w\in T^*$ and for every $\alpha\in (V\cup T)^+$ , if $\alpha \Rightarrow^n w$ then $\alpha \overset{_{lm}}{\Rightarrow}^n w$

I.e

$\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^n w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^n w$

(The leftmost derivation relation is denoted as $\overset{_{lm}}{\Rightarrow}$)

(From a high level point of view the claim says that if some terminal word $w$ can be derived form $\alpha\in (V\cup T)^+$ then there exist a leftmost derivation to derive $w$ from $\alpha$)

---

My try:

Basis

If $n=1$ then we must show that $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^1 w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^1 w$:

Let $w\in T^*$ and let $\alpha\in (V\cup T)^+$ such that $\alpha \Rightarrow^1 w$.

by definition of the $\Rightarrow$ relation we get that:

$\exists \psi,\chi,\gamma\in(V\cup T)^*, \exists A\in V, \alpha = \psi A \chi \land w=\psi \gamma \chi \land (A\rightarrow \gamma)\in P$

Now since $w\in T^*$ and since $w=\psi\gamma\chi$ we get that $\psi \in T^*$ and so:

$\exists \psi\in T^*,\exists \chi,\gamma\in(V\cup T)^*, \exists A\in V, \alpha = \psi A \chi \land w=\psi \gamma \chi \land (A\rightarrow \gamma)\in P$

And we get by definition of $\overset{_{lm}}{\Rightarrow}$ relation that $\alpha \overset{_{lm}}{\Rightarrow} w$ as was to be shown.

Induction hypothesis

Suppose that for some $n=k\geq 1$ we get: $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^k w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^k w$

Induction step

Now we'll prove that: $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^{k+1} w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^{k+1} w$

Let $w\in T^*$ and let $\alpha \in (V\cup T)^+$ such that $\alpha \Rightarrow^{k+1} w$,
And so we get that $\exists \beta \in (V\cup T)^*$ such that $\alpha\Rightarrow\beta\Rightarrow^k w$.
Since $k\geq 1$ we get that $\beta \in (V\cup T)^*V(V\cup T)^*$ and so $\beta\in(V\cup T)^+$.
Now since $w\in T^*$ and since $\beta \Rightarrow^k w$ we get by the induction hypothesis that $\beta \overset{_{lm}}{\Rightarrow}^k w$

Now I do not know how to proceed.

I got that $\alpha \Rightarrow^1 \beta$ but how can I show that $\alpha \overset{_{lm}}{\Rightarrow}^1 \beta$ and from there conclude that $\alpha \overset{_{lm}}{\Rightarrow}^{k+1} w$ using the facts I've shown above?

---

thanks for any help.

Answer 1

Your method of proof can't work, since it implies that every derivation is a leftmost derivation. Indeed, here is a paraphrase of your proof:

Let's prove by induction on the length of the proof that if a word $w$ can be derived from a sentential form $\alpha$ in $n$ steps, then $w$ can be derived from $\alpha$ in $n$ steps using a leftmost derivation. The case $n = 0$ is trivial. Now suppose that $n > 0$, and suppose that the first step of the derivation is $\alpha \Rightarrow \beta$. By induction, $\beta \Rightarrow^* w$ can be converted to a leftmost derivation of length $n-1$, so $\alpha \Rightarrow \beta \Rightarrow^* w$ would be a leftmost derivation of length $n$.

Unrolling the proof, your suggested derivation is actually the same as the original derivation (prove it by induction!), and since not all derivations are leftmost, since can't work.

Concretely, consider the derivation $AB \Rightarrow Ab \Rightarrow ab$. The first step $AB \Rightarrow Ab$ cannot belong to a leftmost derivation. Answering your question, you can't prove that $\alpha \stackrel{lm^1}{\Rightarrow} \beta$, simply because it isn't true.

---

Here is a different approach. Consider the derivation tree used to derive $\alpha$ from $w$. Try to use this tree to generate a leftmost derivation. Note that the length of the derivation is exactly the number of nonleaf nodes in the tree.