128 CONTEXT-FREE LANGUAGES
Figure 3.15: Solution of Example 3.32.To see that this PDA M correctly accepts the language L, we notice that if
we always follow the above rules, there is a computation path of M in which
the stack always contains at most one type of stack symbols. Therefore, for
any x E {u,b)*, we have
(s, x, E) 12 (s, 6 am)if2#a(X)-3#b(X) = 772 2 0, or
if 2rkta(x) - 3#b(x) = -m < 0. Thus, if m # 0, M can move to the final state
p, or the final state pb, accordingly. This shows that if x E L then M must
have an accepting computation path.
Conversely, suppose that we have an accepting computation path on an
input x that ends at state p,. Then, this computation path looks like this:
(s, X,E) t-* (s,EJ+l) t- (pa,,&) I- (Pa,&,&),for some j - > 0, since we do not read any input symbol in state p,, and can
only pop off symbols a in state pa. (In other words, computation paths that
do not follow rule (3) and, hence, leave some symbol b in the stack when we
reach state pa do not accept.) Since we always enforce the matching rules
(1) and (2) before we reach state pa, we must have 2Sjta(x) = 3#b(x) + j + 1
and, hence, x E L. Similar argument works for the case in which M halts
in pb. (See Exercise 4(b) of this section for a different implementation which
enforces rule (3) more carefully.)
In the following, we show two computation paths of M on the same input
ababaab, the first an accepting path and the second rejecting.