Chapter 8

Properties of CFLs

10/31/03

A pumping lemma for CFLs

Let L be an infinite CFL.

Then  some integer

m > 0

such that any w  L

with |w|  m

can be decomposed as

w = uvxyz

with |vxy|  m

and |vy|  1(v and y cannot both be null)

such that uvixyiz  L,i = 0, 1, 2, ....

Idea of Proof

  • Since length of w  L is arbitrarily long

and

the RHS of production is bounded,

we may have a derivation tree of arbitrary length from root to leaf.

  • Number of variables in G is finite

Thus some variable (say A) repeats in the derivation

CS373 Spring 2003 Chapter 8 N. Guydosh Page 1

S * uAz * uvAyz * uvyz

By applying the composite production

A * vAy multiple times (say i)

before using A * x

we get the string

uvixyiz  L generated.
Note on inequalities:
We assume that in the derivations A ==>* vAy, and A ==>* x that only the variable A repeats (and none others – A is the first to repeat as was the case for the first repeating state in the regular pumping lemma). Thus the lengths of v, x, and y depend only on the productionsand are bound independently of w – this give a justification for |vxy|  m.

Also, because we can eliminate all  and unit productions, |vy|  1. One of v or y could be empty if all productions added terminals on to the right (or left).

Example 8.1

Show L = {anbncn : n  0} is not CF.

Opponent picks m.(“pumping value”)

We choose w = ambmcm L

Opponent chooses partition

2:uvxyz

|vxy|  m

|vy|  1

Two possibilities:

Case I:If either v or y contain more than one type of terminal symbol,

Then w2 = uv2xy2z

Contains a b preceded by c

Or, an a preceded by b.

==>  L

Case II:v and x contain substrings of am, bm, or cm

Since at most one of v and y is null,

w2 = uv2xy2z increases the number of at least one, maybe two,

but not all 3 types of terminal symbols.

==>  L

CS373 Spring 2003 Chapter 8 N. Guydosh Page 1

Example 8.1 Analysis

For crossover

v or y may have sequences like:

i2

Case I:...aabb...aabbaabb

i2

Case II:..bbcc..bbccbbcc

i2

Case III:..aabb..bcc..aabb..bcc|aabb..b|cc

In case I, w has b before a==>w2 L

In case II, w has c before b==>w2 L

In case III, w has c before a, etc.==>w2 L

Since not both v and y can be null,

One of the cases must hold.

Thus: w2 L and L is not context free.

Pumping Lemma for Linear Languages

  • Definition 8.1

A CFL L is linear if  linear grammar such that L = L(G)

Note:All linear grammars are CFGs.

Review of linear grammar:

G is linear if, and only if, all productions of the form

A  xBy,x, y *,B  V

orA  zz *

Question:We know that all linear languages are CFLs.

But is converse true?

That is, are all CFL’s linear?

  • Just because a specific grammar is not linear does not imply that the language generated by it is not linear.

That is, perhaps there is an equivalent linear grammar.

  • Use pumping lemma for proving not linear.
  • Pumping lemma for linear languages

Theorem 8.2

Let L be an infinite linear language.

 some positive m

such that  w  L, with |w|  m

w can be decomposed as

w = uvxyz

with |uvyz|  mDoes not involve x, “anchored” on the left and right

|vy|  1Same as before

such that:

uvixyiz  L

i = 0, 1, 2, ....

Strings v and y to be pumped must be located within m symbols of the left and right ends of w, respectively – an anchoring property! (compare to regular pumping lemma).

x can be of arbitrary length within constraints of inequalities.

See example 8.6, p. 218.

Regular and Context Free Comparison

Property / Regular / Context Free
Closed under , concatenation, * / Yes / Yes
Closed under  / Yes / No
Closed under complementation / Yes / No
Closed under homomorphism / Yes / ?
Closed under right quotient / Yes / ?
Closed under symmetric difference L1L2 / Yes / No – why?
Closed under reversal / Yes / ?
Algorithm for determining if L is , finite,  / Yes / Yes
Algorithm for determining if L1 = L2 / Yes / No - see p. 219

A special for CFL’s: Theorem 8.5:

The intersection of a Context free language with a Regular Language is context free

Sometimes this can be a powerful theorem in proving properties of a language.

CS373 Spring 2003 Chapter 8 N. Guydosh Page 1