To show that M accepts any w ∈ L (G), consider the partial leftmost
derivation
If M is to simulate this derivation, then after reading a 1 a 2 …a n , the stack must
contain A 1 A 2 …A m . To take the next step in the derivation, G must have a
production
A 1 → bB 1 …B k .
But the construction is such that then M has a transition rule in which
(q 1 , B 1 …B k ) ∈ δ (q 1 , b, A 1 ),
so that the stack now contains B 1 …B k A 2 …A m after having read a 1 a 2 …a n b.
A simple induction argument on the number of steps in the derivation then
shows that if
then
Using (7.1) and (7.3) we have
so that L (G) ⊆ L (M).
To prove that L (M) ⊆ L (G), let w ∈ L (M). Then by definition
But there is only one way to get from q 0 to q 1 and only one way from q 1 to q f .
Therefore, we must have