130 CONTEXT-FREE LANGUAGES
Figure 3.17: Solution of Example 3.34.Example 3.34 Construct a PDA M that accepts the language
L = -b E {a, b}* ( 3#a(w) 5 5#b(W) 5 4#a(w)}*
Solution. This problem is similar to the last one. We follow the following
rules to match symbols a with symbols b:
(1) Each input symbol a is worth either three or four
each input symbol b is worth five stack symbols b.stack symbols a, and
(2) Each stack symbol a needs to match a stack symbol b.
(3) We perform the matching whenever it is possible.
We show this PDA M in Figure 3.17. Note that we have added a transition
(s,~) E S(p3, &,E) that allows M to move from state p3 to state s without
changing the stack. Therefore, M can treat an input symbol a as either three
stack symbols a or four stack symbols a.
To see that this PDA works correctly, first assume that w E L. Let #a(w) =
i, #b(w) = j. Then, we must have 3i < 5j < 4i. Equivalently, there must
be an integer k, 0 < k < i, such that !!?j = ?k + 4(i - k). (E.g., if i = 18,
then 11 < j < 14. We check that 5.11 = 3 l 17 + 4 l 1, 5 l 12 = 3. 12 + 4.6,
5.13 = 3:7+411, and 5.14 = 32+4*16.) Therefore, there is a computation
path of M accepting w. Conversely, it is clear that if w $ L, then there is no
way to match stack symbols a and b evenly and so M does not accept w. 0
Exercise 3.4
- For each of the following languages L, construct a PDA to accept L. In
addition, for each given string x E L, show an accepting computation