stack in the derivation of R-AVG $G'$.

Case II

:   Initial nonterminal $S$ of GNF $G$ derives string $\alpha=\beta\beta'$ in more than one step iff there is a left-most derivation $S \stackrel{*}{\Rightarrow} \beta A
       \Rightarrow
       \beta\beta'$. GNF $G$ contains production $A \rightarrow \beta'$ iff R-AVG $G'$ contains production $A \rightarrow \beta'$ with the equation . By the next lemma: $S \stackrel{*}{\Rightarrow}
       \beta A$ iff $S \stackrel{*}{\Rightarrow} \beta A$ with the empty stack. Hence $S$ derives $\alpha$ for GNF $G$ iff $S$ derives $\alpha$ with empty stack for R-AVG $G'$.

Start nonterminal $S$ derives $\alpha A\gamma$ ($\alpha \in \Sigma^+,
A\gamma \in (N \setminus \{S\})^+$) in a left-most derivation of GNF $G$ if, and only if, nonterminal $S$ derives $\alpha A$ with stack $\gamma\$$ (\$ is the bottom-of-stack symbol) in the derivation of R-AVG $G'$.

The lemma is proven by induction on the length of the derivation.

Basis

:   If $S$ derives $\alpha A \gamma$ in one step, then GNF $G$ contains production $S \rightarrow \alpha A \gamma$ and R-AVG $G'$ contains production $S \rightarrow \alpha A$ with stack $\gamma\$$. If $S$ derives $\alpha A$ with stack $\gamma\$$ in one step, then R-AVG $G'$ contains production $S \rightarrow \alpha A$ with stack 