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.
You have $\alpha\Rightarrow\beta\overset{lm}\Longrightarrow^k w$, so there are $\gamma,\delta,\zeta\in(V\cup T)^*$ and $A\in V$ such that $\alpha=\gamma A\delta$, $\beta=\gamma\zeta\delta$, and $A\to\zeta$ is in $P$. If $\gamma\in T^*$, you’re done: we have a leftmost derivation. If not, $\gamma=\gamma_1B\gamma_2$ for some $\gamma_1\in T^*$, $B\in V$, and $\gamma_2\in(V\cup T)^*$. Thus, $\beta=\gamma_1B\gamma_2\zeta\delta$, where $\gamma_1\in T^*$.
The first step in the leftmost derivation $\beta\overset{lm}\Longrightarrow^k w$ must therefore use some production $B\to\eta$ in $P$:
$$\beta\overset{lm}\Longrightarrow\gamma_1\eta\gamma_2\zeta\delta\overset{lm}\Longrightarrow^{k-1}w\;.\tag{1}$$
Reverse the order of the first two steps: first apply the production $B\to\eta$ to get
$$\alpha=\gamma A\delta=\gamma_1B\gamma_2 A\delta\overset{lm}\Longrightarrow\gamma_1\eta\gamma_2A\delta\;,$$
where $\gamma_1\in T^*$. Now we know from $(1)$ that
$$\gamma_1\eta\gamma_2A\delta\Rightarrow\gamma_1\eta\gamma_2\zeta\delta\overset{lm}\Longrightarrow^{k-1}w\;,$$
so in particular $\gamma_1\eta\gamma_2A\delta\Rightarrow^kw$. By the induction hypothesis $\gamma_1\eta\gamma_2A\delta\overset{lm}\Longrightarrow^kw$, and $\gamma_1\in T^*$, so
$$\alpha\overset{lm}\Longrightarrow\gamma_1\eta\gamma_2A\delta\overset{lm}\Longrightarrow^kw$$
and hence $\alpha\overset{lm}\Longrightarrow^{k+1}w$, as desired.