Let .
Basis (i = 1)
contains
is a production of G.

Induction (i > 1)
Let x = ay and

y can be written as such that

pops from the stack for the first time.

That is, states
Where , such that

by fewer than i moves.

By hypothesis, therefore,
(I)
for

From the first move

We get