we see that this can be so if and only if
Consequently L(M) = L(G).
EXERCISES
1. Show that the pda constructed in Example 7.6 accepts the string aaabbbb that
is in the language generated by the given grammar.
2. Prove that the pda in Example 7.6 accepts the language L = {a n+1 b 2n : n ≥ 0 }.
3.Construct an npda that accepts the language generated by the grammar
4. Construct an npda that accepts the language generated by the grammar S →
aSSS|ab.
5. Construct an npda corresponding to the grammar
6. Construct an npda that will accept the language generated by the grammar G
= ({S, A},{a, b},S,P), with productions S → AA |a, A → SA| b.
7. Show that Theorems 7.1 and 7.2 imply the following. For every npda M,
there exists an npda with at most three states, such that L (M) = L ( ).
8. Show how the number of states of in the above exercise can be reduced to
two.
9. Find an npda with two states for the language L = {a n b n+1 : n ≥ 0}.
10. Find an npda with two states that accepts L = {a n b 2n : n ≥1}.