(^126) CONTEXT-FREE LANGUAGES
b,E /b
b,a IE c, b/e
Figure 3.13: Solution to Example 3.30.
0 a
a, E/aFigure 3.14: Solution to Example 3.31.
..
Solution. First, we consider the language L1 = {a”~ 1 i,j > 0,2i = 3j). For a
string aibj to be in L1, it must be true that i = 3k and j z2lc for some Ic > 0.
Thus, for each symbol a of the input, we can push two copies of symbol a Lto
the stack. Then, for each symbol b we read from the input, we match it with
three u’s in the stack. How do we push two symbols au into the stack? We
can push one a into the stack and then move to a temporary state in which we
push another a into the stack. Similarly, we can match each input symbol b
with one stack symbol a first, and then move to another two temporary states
to pop up two more symbols a. A PDA based on this idea is constructed in
Figure 3.14(a).
Next, we consider the language L. The idea here is to use the above PDA
to match every b with one and a half u’s. After that, we nondeterministically
move to state pa or state pb to handle the case of 2i > 3j or 2i < 3j, re-
spectively. To get to state p,, we need to pop up at least one more symbol a
from the stack without a matching b. When we reach state pa, we clean up
the stack and accept the input. To get to state pb, we need to read at least
one more symbol b. When we reach state pb, we read off all symbols b on the