Problem Solving in Automata, Languages, and Complexity

138 CONTEXT-FREE LANGUAGES

We observe that the construction in the proof of Theorem 3.37 is very
tedious and the resulting context-free grammar is often too complicated to
understand. For instance, in Example 3.34, we had a relatively simple PDA
for the language {w E {a$}* 1 3#ta(w) < 5#b(w) < 4#a(w)}, but an equiv-
alent context-free grammar for this language is very difficult to construct (cf.
Example 3.16). N evertheless, this equivalence result is a useful tool for prov-
ing the closure properties of context-free languages. In Theorem 3.17, we have
used simple constructions of context-free grammars to show that the class of
context-free languages are closed under union, concatenation and Kleene clo-
sure. In the following, we use pushdown automata to prove more closure
properties of context-free languages.
First, we consider the operation of intersection.

Example 3.39 Show that if A is a regular language and B is a context-free

language, then A n B is a context-free language.

Proof. Let MA = (&A, C, SA, SA, FA) be a DFA accepting A and & =

(QB, C, I’B, SB, sg, FB) a PDA accepting B. Similar to the product finite au-

tomaton, we can construct a product pushdown automaton M which simulates

MA and MB in parallel. The PDA M accepts an input string z if both MA

and A& accept it.

The detail is as follows: We define M = (Q, C, I’, 6, s, F) , where Q =

QA x QB, F = I’B, s = [sA,sB], F = FA x FB, and

where p E I’ U {E}. It is clear that L(M) = A n B.^0

Can we use the above proof technique to show that context-free languages

are closed under intersection? That is, can we construct a product pushdown

automaton that simulates two pushdown automata in parallel? The answer is

no, since we do not know how to simulate two stacks with only one stack. In

fact, we will show, in Corollary 3.48, that the intersection of two context-free

languages is not necessarily context-free. Thus, such a product pushdown

automaton does not exist.

On the other hand, representing a language as an intersection of several

context-free languages can still be helpful in determining whether its comple-

ment is context-free or not.

Example 3.40 Show that L = (0, 1)” - {(Omlm)n 1 m, n > - 1) is a context-

free language.

Proof. We first show that I; is the intersection of two context-free languages.

Let A = {Omlm 1 nz > - l}+ and B = {O}+{lmOm I nz > l}*{l}+. - That is,