Let
We show by induction that

Basis (i = 1)
If then
(q, x, A) must contain .

Induction
Let

Then x can be written as
where
,
in fewer than i steps.
by hypothesis
(II)

From the first step,

These together
.