Problem Solving in Automata, Languages, and Complexity

3.5 Pushdown Automata and Context-Free Grammars 141

S(q1, Xyz) = S(qj, yZ) = s(4kT z) = !It E Fe

Correspondingly, the PDA @ accepts w as follows: It begins with a simulation
of M on x. At the end, it reaches the configuration (qj, Z, xR). Next, it applies
the instructions of type (iv) to get to the following configuration:

Then, it applies instructions of type (v) to the above configuration. The
computation path that guesses the correct y in the first track leads to the
following configuration:

where qii, = qt E F, because S(qk, z> = qt. Thus, this computation accepts w.
Conversely, it is easy to see that any accepting computation path of E must
follow this pattern. In particular, it must move from a state qi in Q to a state
in Q”+l after it reads 1wi/2 symbols, for otherwise the stack size is different
from the size of the remaining input and X? cannot accept. In addition, when
it finishes the input and gets the empty stack, the state in the first track must
correspond to S(qj, y) for some y of length 1 yI = 1x1. Therefore, the design of
the final set F guarantees that there is a computation path in M accepting
xyx. This proves that G accepts exactly set i. cl

Exercise 3.5

1. For each of the following context-free grammars G, following the pro-

cedure of Theorem 3.35 to construct a PDA that accepts the language

L(G):

(a) S -+ & 1 aSbS 1 bSaS.

(b) S + E 1 SS 1 aSb.

(c), The grammar of Solution 2 to Example 3.6.

(d) The unambiguous grammar of Example 3.24(b).

2. For each of the following PDA’s M, following the procedure of Theorem
   3.37 to construct a context-free grammar that generates the language
   L(M):

(a) The PDA of Example 3.30.

(b) The PDA of Figure 3.14(a) (for language {aibj I 2i = 3j)).

3. Construct pushdown automata to accept the following languages:
   (a) {Onlm I m # n,m # 2n,m # 3n).
   (b) {aWck I i # j or j # k or i # k}.

• (c) (0, l}* - {(Onl)n I n > - 1).