and
The rest of the solution is then essentially the same as 4(a).
9. This is a pda that makes no use of the stack, so that is, in effect, a finite
accepter. The state transitions can then be taken directly from the pda, to give
11. Trace through the process, taking one path at a time. The transition from q 0
to q 2 can be made with a single a. The alternative path requires one a,
followed by one or more b’s, terminated by an a. These are the only
choices. The pda therefore accepts the language
14. Here we are not allowed enough states to track the switch from a’s to b’s
and back. To overcome this, we put a symbol in the stack that remembers
where in the sequence we are. For example, a solution is
We have only two states, the initial state q 0 and the accepting state q f . What
would normally be tracked by different states is now tracked by the symbol
in the stack.
16. Here we use internal states to remember symbols to be put on the stack. For
example,