with
11. What language is accepted by the npda M = ({q 0 , q 1 , q 2 }, {a, b}, {a, b, z}, δ,
q 0 , z, {q 2 }) with transitions
12. What language is accepted by the npda in Example 7.4 if we use F = {q 0 , q f
}?
13. What language is accepted by the npda in Exercise 11 above if we use F =
{q 0 , q 1 , q 2 }?
14. Find an npda with no more than two internal states that accepts the language
L (aa*ba*).
15. Suppose that in Example 7.2 we replace the given value of δ (q 2 , λ, 0) with
What is the language accepted by this new pda?
16. We can define a restricted npda as one that can increase the length of the
stack by at most one symbol in each move, changing Definition 7.1 so that
The interpretation of this is that the range of δ consists of sets of pairs of the
form (q i , ab), (q i , a), or (q i , λ). Show that for every npda M there exists such
a restricted npda such that L (M) = L ( ).
11. What language is accepted by the npda M = ({q 0 , q 1 , q 2 }, {a, b}, {a, b, z}, δ,
q 0 , z, {q 2 }) with transitions
12. What language is accepted by the npda in Example 7.4 if we use F = {q 0 , q f
}?
13. What language is accepted by the npda in Exercise 11 above if we use F =
{q 0 , q 1 , q 2 }?
14. Find an npda with no more than two internal states that accepts the language
L (aa*ba*).
15. Suppose that in Example 7.2 we replace the given value of δ (q 2 , λ, 0) with
What is the language accepted by this new pda?
16. We can define a restricted npda as one that can increase the length of the
stack by at most one symbol in each move, changing Definition 7.1 so that
The interpretation of this is that the range of δ consists of sets of pairs of the
form (q i , ab), (q i , a), or (q i , λ). Show that for every npda M there exists such
a restricted npda such that L (M) = L ( ).