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

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.

• If my question and my suggested proof is not clear please tell me how to revise it. Dec 30 '15 at 15:51
• I've got some additional answer on Math Exchange: math.stackexchange.com/questions/1594169/… Dec 31 '15 at 7:18
• In the future, don't ask the same question on two sites; this is frowned upon. Dec 31 '15 at 7:48

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$.
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.