Problem Solving in Automata, Languages, and Complexity

3.6 Pumping Lemmas for Context-Free Languages 153

• Example 3.56 A language L over a singleton aZphubet (0) is context-free
  if and only if it is regulur.

Proof. Since a regular language is context-free, it suffices to show the forward
direction. Suppose L C
semilinear; therefore +(X)

{0}* is context-free. By Parikh’s lemma, 4(L) is
is a union of finitely many linear sets Tl,... , Tn,
where each Ti is a one-dimensional linear set. Let Li = (0” 1 nz E Ti}; that
is, 4(b) = Ti. Then, it is obvious that L = Uy=, Li. Since a finite union of
regular languages is still regular, it suffices to prove that each Li is regular,
for i = 1,... , n.
Fix an i E (1,... , 72). Since $( Li) is linear, we can write

+(Li) = {u+&-njvj j ml,ma,***,rnj 2 O},

j=l

where u, VI, 212, l. l , ?& are positive integers. It follows that

Li = ()“(()vl)*(()v2)*... (Ovi)*,

and so it is regular. cl

Example 3.57 Show that {On2 ( n > l} is not an intersection of k context-
free languages over alphabet (0, 1) f& any k.

Proof. First, we note that for any context-free language L over (0, l}, L n 0
is a regular language: By Example 3.39, L n 0 is context-free and so, by
Example 3.56, it is regular.
Now, for the sake of contradiction, suppose that {On2 1 n > 1) is an in-
tersection of k context-free languages L1, L2, l.. .Lk over alphabet (0, 1) for
some k > 1. Then it is also the intersection of L1 n 0 , L2 n O,... , LI, n O.
Since each of LlnO, L:!nO,... , L&O is regular, we know that {On2 1 n > 1)
is also regular. This is a contradiction (see Exercise 3(b) of Section 2.7).- •I

Parikh’s lemma cannot replace the pumping lemma. For instance, the set
L1 = (ubc)” and L2 = {unbncn I n > - 0) have the same counting set q5(Ll) =
+(L2), but one of them is context-free and the other is not. However, it
sometimes gives us a stronger pumping property of a given language, allowing
us to “pump” a specific part of a string to produce a contradiction. The
following are some examples.

• Example 3.58 Show that the language L = {u”P I n # m2} is not
  context-free.

Proof. This result is difficult to prove by the pumping lemma. For instance,
suppose that we start with a string w = umbn, with n > m2. Then, when
we apply the pumping lemma to w to get w = uv~yyz, we cannot handle the