11. Show that the npda in Example 7.8 accepts L (aa*b).
12. Show that the grammar in Example 7.8 generates the language L (aa*b).
13.In Example 7.8, show that the variable (q 0 zq 1 ) is useless.
14. Use the construction in Theorem 7.1 to find an npda for the language in
Example 7.5, Section 7.1.
15. Find a context-free grammar that generates the language accepted by the
npda M = ({q 0 ,q 1 }, {a, b}, {A, z},δ, q 0 , z, {q 1 }), with transitions
δ(q 0 , a,z) = {(q 0 , Az)},
(q 0 ,b, A) = {(q 0 , AA)},
δ(q 0 , a, A) = {(q 1 )λ}
16. Show that for every npda there exists an equivalent one satisfying conditions
1 and 2 in the preamble to Theorem 7.2.
17. Give full details of the proof of Theorem 7.2.
18. Give a construction by which an arbitrary context-free grammar can be used
in the proof of Theorem 7.1.
19. Does the grammar in Example 7.8 still have any useless variables?
7.3 Deterministic Pushdown Automata and
Deterministic Context-Free Languages
A deterministic pushdown accepter (dpda) is a pushdown automaton that
never has a choice in its move. This can be achieved by a modification of
Definition 7.1.
Definition 7.3
A pushdown automaton M = (Q, Σ, Γ, δ, q 0 , z, F) is said to be deterministic if it is
an automaton as defined in Definition 7.1, subject to the restrictions that, for
every q ∈ Q, a Σ ∪{λ} and b ∈ Γ,