3.4 Pushdown Automata 127
input tape and accept the input.
There is a subtle problem with the second case. That is, it is possible that
i is not a multiple of 3, and M might be stuck at state q1 or q2, trying to pop
a symbol a from an empty stack. To solve this problem, we note that if M has
an empty stack at state q1 or q2, it means that M has recognized the condition
of 2i < 3j. Thus, we can move directly to the final state ~36 from these two
states without popping up any more symbols a from the stack. (There is no
problem with the first case, since we can always match all input symbols b
with the symbols a in stack when 2i > 3j.)
The PDA for L is shown in Figure 3.14(b). The following is an accepting
path for input a4b4:(s, a4b4, E) I- (sl, a3b4, a) t- (s, a3b4, aa) i-* (s, b4, as)
t- (q, b4, as) f- (ql, b3, a7) I- (42, b3, a6) t- (q, b3, a5)
c (q,bb,aa) t- (q+,a) l- (q2,O) t- (P&E) b- (PWV). clL = ix e wG* I2#a(z) # 3#&)}.Solution. This problem looks like the last one, but there is a critical difference
that, in this problem, the symbols a and b may occur in any order. Therefore,
we may read a symbol b before we meet any matching symbol a, In this case,
we need to push the symbol b into the stack in order to perform the matching
later. The general rules here are:
(1) Each input symbol a is worth two stack symbols a, each input symbol
b is worth three stack symbols b.
(2) Each stack symbol a needs to match a stack symbol b.
(3) We need to perform a matching if the new input symbol is different from
the one at the top of the stack.
(4) If the new input symbol is the same as the top of the stack symbol, then
we always push the new symbol into the stack.
There are some exceptional cases we need to take care of before we can
complete the design of the PDA: If there are not enough stack symbols to
match the new input symbol, then we push the extra worth of stack symbols
into the stack. For instance, if we read an input symbol b and the stack has
only one symbol a, then we pop off this symbol a and then push in two stack
symbols b. We implement these ideas in the PDA M shown in Figure 3.15.
In this PDA, we use state sr to handle the input symbol a. When an input
symbol a is read, we either match it with a stack symbol b or push a stack
symbol a into the stack. Then, we move to state sr. At state sl, we pop off
another stack symbol b or push another stack symbol a into the stack; and
then we move back to state s. We use states q1 and q2 to handle the input
symbol b in a similar way.