Problem Solving in Automata, Languages, and Complexity

142 CONTEXT-FREE LANGUAGES

* (d) (0, q* - {h#b+1 I bi is the binary representation of i, i > - 1).

4. Show that if L is a regular language, then each of the following languages
   is context-free:

(a) {Z E L 137 = eR}.

* (b) {WY I (%2) [I4 = 14 = IYI = IZI, wqv E L]).

* (4 {YX I P-4 4 [I4 = 14 = IYI = 14, wvx E L]}.

* (d) (22 1 IWI = 1x1 = lyl = (“l,wzyx E L}.

5. Show that L1 \ L2 is a context-free language, if L1 is context-free and
   L2 is regular.


6. A two-stack pushdown automaton @-stack PDA) is a PDA with two
   pushdown stacks. At each move, M can read, in addition to an input
   symbol, the top symbols of both stacks, and to write symbols to both
   stacks. Formally, a 2-stack PDA is a 6-tuple M = (Q, C, I, S, s, F),
   where Q, C, I’, s, F are the same as those of a PDA, and S is a transition
   function

s :& x (c u {E}) x (ru {E})2 + 2QX(rU{E1)2*

Let a E CU{E}, and ~1, ~2, ~1,212 E I’ U {E}. Then, an instruction

(p, ~1,212) E 5(q, a, ~1, u2), indicates that the PDA M reads the input a,

the top symbol u1 of stack 1, the top symbol ~2 of stack 2, and then it

moves to state p, repaces ~1 by v1 and replaces ~2 by 212.

(a) Define formally the notion of configurations and successor config-

urations of a 2-stack PDA.

(b) Construct a 2-stack PDA to accept the language {unbncn I n > - 0).

(c) Construct a 2-stack PDA to accept the language {a”bmc”d” I

n > - m).

* 7. A pushdown automaton M is called a linear-bounded PDA if there is a

constant c > 0 such that the size of the stack of M, during its computa-

tion on any input q is bounded by CIJZI. Show that the class of languages

accepted by linear-bounded PDA’s is exactly the class of context-free

languages.

3.6 Pumping Lemmas for Context-Free Languages

In this section, we prove a pumping lemma for context-free languages which is
analogous to the pumping lemma for regular languages. We demonstrate how
to apply this lemma and its stronger forms to prove that a given language is
not context-free.
Let G = (V, C, R, S) b e a context-free grammar. Assume that IV1 = rn
and that, for every rule A -+ z in R, 1x1 < - d for some constant d > 0. This