1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If my question and my suggested proof is not clear please tell me how to revise it. $\endgroup$ – MathNerd Dec 30 '15 at 17:46
  • $\begingroup$ I've got some answer on CS Exchange: cs.stackexchange.com/questions/51292/… $\endgroup$ – MathNerd Dec 30 '15 at 19:05
  • 1
    $\begingroup$ In the future, don't ask the same question on several sites; this is frowned upon. $\endgroup$ – Yuval Filmus Dec 31 '15 at 7:49
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @MathNerd: You're very welcome. $\endgroup$ – Brian M. Scott Dec 31 '15 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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