and finally
to recognize a successful match.
The sequence of moves in accepting abba is
The nondeterministic alternative for locating the middle of the string is taken at
the third move. At that stage, the pda has the instantaneous descriptions (q 0 , ba,
baz) and has two choices for its next move. One is to use δ (q 0 , b, b) = {(q 0 , bb)}
and make the move
the second is the one used above, namely δ (q 0 , λ ,b) = {(q 1 , b)}. Only the latter
leads to acceptance of the input.
EXERCISES
1. Find a pda with fewer than four states that accepts the same language as the
pda in Example 7.2.
2. Prove that the pda in Example 7.5 does not accept any string not in {ww R }.
3. Construct npda's that accept the following regular languages.
(a) L 1 = L (aaa*b).
(b) L 1 = L (aab*aba*).
(c) the union of L 1 and L 2 .
(d) L 1 − L 2 .