Problem Solving in Automata, Languages, and Complexity

146 CONTEXT-FREE LANGUAGES

Recall that for any language L, MAX(L) is the set of strings 2 E L such
that g is not a proper prefix of any string in L. It was shown in Exercise 1 (a)
of Section 2.6 that regular languages are closed under the MAX operation.

Corollary 3.48 The class of context-free languages is not closed under in-
tersection, complementation, or the MAX operation.

Proof. Note that {anbncm 1 r-n+ > 0) and {a”bncn 1 nz,n > 0) are two
context-free languages. Their inter&tion is {unbncn 1 n - > O}rwhich is not
context-free, as proved in Example 3.44. Thus, context-free languages are not
closed under intersection.
For complementation, we note that, by Example 3.20, the complement of
{ww 1 w E (0, l}*} is a context-free language. Thus, Example 3.45 showed
that context-free languages are not closed under complementation. (This
result also follows from De Morgan’s Law, since we already know that context-
free languages are closed under union, but not closed under intersection.)
Finally, for the MAX operation, we consider the language L = {&V I i >
k or j > k}. It is easy to verify that L is context-free. Clearly, MAX(L) =
{u%V~ k = max{i,j} }. Th ere f ore, by Example 3.47, context-free languages
are not closed under MAX. cl

Although context-free languages are not closed under intersection, we know,

by Example 3.39, that the intersection of a context-free language and a regular

language must be context-free. This weaker closure property is still helpful in

proving a language not context-free.

Example 3.49 Show that L = -b E h b, cl* I #a(w) = #b(W) = #c(w)} is
not context-free.

Proof. We note that the language L1 = {unbncn I n > 0) is equal to Lnu*b*c*.

By Example 3.39, we know that L cannot be context-free, for otherwise L1

would also be context-free, contradicting Example 3.44. q

Example 3.50 Show that if a set L has the property that every subset of L
is context-free, then L must be a finite set.

Proof. Suppose, for the sake of contradiction, that L is infinite. Then, there
is an infinite subset A of L having the following property: For any w E A, all
strings x of length IwI + 1 < - 1x1 < 21 - w I are not in A. Indeed, we can construct
set A recursively as follows:

Initially, we let A = 8. At stage 0, we select a shortest nonempty

string wo E L and add it in A. Assume that by the end of stage

e, we have selected strings WO, WI,... , we in L with the properties

lwij > 2lw;-ll for all i = 1,.. ., e, and have added them to A.

At stage e + 1, we select a string we+1 in L with the property

l&+11 > 2lwel and add it to A.