with three states, q 0 , q 1 , q f . The state q 1 can be eliminated if we use a special
stack symbol z 1 to mark it. A complete solution is
11. There must be at least one a to get started. After that, δ (q 0 , a, A) = {(q 0 ,
A)} simply reads a’s without changing the stack. Finally, when the first b is
encountered, the pda goes into state q1, from which it can only make a λtransition to the final state. Therefore, a string will be accepted if and only
if it consists of one or more a’s, followed by a single b.
Section 7.3
4. At first glance, this may seem to be a nondeterministic language, since the
prefix a calls for two different types of suffixes. Nevertheless, the language
is deterministic, as we can construct a dpda. This dpda goes into a final state
when the first input symbol is an a. If more symbols follow, it goes out of
this state and then accepts a n b n . Complete solution:
where F = {q 2 , q 3 }.
9. The solution is straightforward. Put a’s and b's on the stack. The c signals the
switch from saving to matching, so everything can be done deterministically.
11. There are two states, the initial, nonaccepting state q 0 and the final state q 1 .
The pda will be in state q 1 unless a z is on top of the stack. When this
happens, the pda will switch states to q 0 . The rest is essentially the same as