Now let us write w = a 1 a 2 a 3 …a n . Then the first step in
must be a rule of the form (7.2) to get
But then the grammar has a rule of the form S → a 1 u 2 , so that
Repeating this, writing u 1 = Au 2 , we have
implying that A → a 2 u 3 is in the grammar and that
This makes it quite clear at any point the stack contents (excluding z) are
identical with the unmatched part of the sentential form, so that (7.4) implies
In consequence, L (M) ⊆ L(G), completing the proof if the language does not
contain λ.
If λ ∈ L, we add to the constructed npda the transition
so that the empty string is also accepted.
1 Because of the nondeterminism, such a change is of course not necessary.
Example 7.7
Consider the grammar
must be a rule of the form (7.2) to get
But then the grammar has a rule of the form S → a 1 u 2 , so that
Repeating this, writing u 1 = Au 2 , we have
implying that A → a 2 u 3 is in the grammar and that
This makes it quite clear at any point the stack contents (excluding z) are
identical with the unmatched part of the sentential form, so that (7.4) implies
In consequence, L (M) ⊆ L(G), completing the proof if the language does not
contain λ.
If λ ∈ L, we add to the constructed npda the transition
so that the empty string is also accepted.
1 Because of the nondeterminism, such a change is of course not necessary.
Example 7.7
Consider the grammar