Problem Solving in Automata, Languages, and Complexity

3.4 Pushdown Automata 129

b,a /E

a,b /E b,c Lb

a, E/a

Figure 3.16: Solution of Example 3.33.

(s, ababaab, E) I- (~1, babaab, a) t- (s, babaab, aa) I- (ql, abaab, a)

I- (q2, abaab, E) t- (s, abaab, b) t- (~1, baab, E) I- (s, baab, a)

I- (41, aab, E) I- (q2, aab, b) I- (s, aab, bb) t- (~1) ab, b)

t- (s, ab, E) t- (~1, b, a) i-- (s, b, aa) t-- (qlIE, a) t- (q2, GE)

i- (S,&,b) i- (Pb,&,+

(s, ababaab, E) F (s, aab, bb) t- (~1, ab, abb) t- (s, ab, aabb)

I- (~1, biaaabb) I- (s, b, aaaabb) I- (ql, E, aaabb) k (q2, E, aabb)

I- (s, E, abb) I- (pa, E, bb) I-?.^0

Example 3.33 Construct a PDA M that accepts the following language:

Iw E ia, b}* 1 #a(w) 5 #b(W) 5 2#,(4}.
SoZution. In this problem, we need to match symbols a and b such that each
symbol a is matched with at least one and at most two symbols b. This
presents a new problem: for each symbol a, should we push in one stack
symbol a or two stack symbols aa? If we push in only one stack symbol a,
then we may not be able to check whether #b(W) < 2#a(w) when we find
that there are extra b’s. Likewise, if we push in two-stack symbols aa, then
we have no way to verify whether Sjta(w) - < #b(W). The solution here is to
use the nature of nondeterminism of PDA’s to push in either one a or two a’s.
That is, we nondeterministically divide all occurrences of symbol a into two
parts. Each symbol a in the first part is to be matched with one symbol b, and
each symbol a in the second part is to be matched with two symbols b. It is
obvious that if this matching succeeds for any partition of symbols a, we must
have #a(w) 5 #b(W) 5 2#a(w)- c onve’=+ if #a(w) 5 #b(w) 5 2#a(w),
then there is such a partition of symbols a that will match a’s and b’s evenly.
Based on the above idea, we present the PDA in Figure 3.16. An accepting
computation path for input baabbabb is as follows:

(s, baabbabb, E) I- ( s, aabbabb, b) I- (p, abbabb, E) I- (s, abbabb, a)

I- (s, bbabb, au) t- (s, babb, a) I- (s, abb, E) k (p, bb, a) I- (s, bb, au)

I- (%b4) I- (S,v)* cl