The Pumping Lemma For Context-free Languages

The Pumping Lemma for Context-Free Languages

1

Take an infinite context-free language Generates an infinite number of different strings

Example:

S  AB A  aBb B  Sb Bb 2

S  AB A  aBb B  Sb Bb

In a derivation of a long string, variables are repeated

A derivation:

S  AB  aBbB  abbB  abbSb  abbABb  abbaBbBb   abbabbBb  abbabbbb 3

Consider now an infinite context-free language

Let

G

Take

G

L

be the grammar of

L  {}

so that I has no unit-productions no  -productions 4

Let

p = (Number of productions) x

(Largest right side of a production)

Let

m  p 1

Example G : S  AB

A  aBb B  Sb Bb

p  4  3  12 m  p  1  13 5

Take a string w L(G ) with length | w | m

We will show: in the derivation of w a variable of G is repeated

6

*

Sw

v1  v2    vk  w

S  v1

7

v1  v2    vk  w | vi || vi 1 |  f

maximum right hand side of any production

| w | k  f

m | w | k  f

pk f 8

v1  v2    vk  w pk f

p k f

Number of productions in grammar

9

v1  v2    vk  w k

Number of productions in grammar

Some production must be repeated

v1    a1Aa2    a3 Aa4    w Repeated variable

S  r1 A  r2 B  r2  10

w L(G )

| w | m

Derivation of string

w

S    a1Aa2    a3 Aa4    w Some variable is repeated

11

Derivation tree of string

w S

z

u Last repeated variable

w  uvxyz

A

y

v repeated A

u, v, x, y, z : Strings of terminals

x

12

S Possible derivations: 

A

S  uAz 

A  vAy

z

u

y

v

A



A x

x

13

We know: 



A  vAy

S  uAz



A x

This string is also generated: 

*

S  uAz  uxz

0

0

uv xy z 14

We know: 





A  vAy

S  uAz

A x

This string is also generated:



*

*

S  uAz  uvAyz  uvxyz The original

w  uv xy z 1

1

15

We know: 

S  uAz





A  vAy

A x

This string is also generated:



*

*

*

S  uAz  uvAyz  uvvAyyz  uvvxyyz 2

2

uv xy z 16

We know: 

S  uAz



A  vAy

This string is also generated:  *



A x

*

S  uAz  uvAyz  uvvAyyz  *

*

 uvvvAyyyz  uvvvxyyyz 3

3

uv xy z 17

We know: 

S  uAz



A  vAy



A x

This string is also generated:

* uAz  * uvAyz  * uvvAyyz * S * uvvvAyyyz  *  * uvvvvAy  yyyz *  * uvvvvxy yyyz  i

i

uv xy z 18

Therefore, any string of the form

i

i

uv xy z is generated by the grammar

i0 G

19

Therefore,

knowing that

uvxyz  L(G )

we also know that

uv xy z  L(G ) i

i

L(G )  L  {}

i

i

uv xy z  L 20

S

z

u

A

y

v

A

x

Observation: Since

A

| vxy |  m

is the last repeated variable 21

S

z

u

A

y

v

A

x

Observation:

| vy |  1

Since there are no unit or

-productions

22

The Pumping Lemma: For infinite context-free language there exists an integer

m

w  L,

for any string

L

such that

| w | m

we can write

w  uvxyz

with lengths

| vxy | m and | vy | 1

and it must be: i i

uv xy z  L,

for all i  0 23

Applications of The Pumping Lemma

24

Non-context free languages

{a b c : n  0} n n n

Context-free languages

{a b : n  0} n n

25

Theorem: The language n n n

L  {a b c : n  0}

is not context free

Proof:

Use the Pumping Lemma for context-free languages

26

L  {a b c : n  0} n n n

Assume for contradiction that

L

is context-free

Since L is context-free and infinite we can apply the pumping lemma

27

L  {a b c : n  0} n n n

Pumping Lemma gives a magic number such that:

Pick any string

We pick:

w L

with length

m

| w | m

wa b c

m m m

28

L  {a b c : n  0} n n n

wa b c

m m m

We can write:

with lengths

w  uvxyz

| vxy | m

and

| vy | 1 29

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Pumping Lemma says:

uv xy z  L i

i

for all

i0 30

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

We examine all the possible locations of string vxy in w

31

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

Case 1:

vxy

| vxy | m is within

a

| vy | 1 m

m m m aaa...aaa bbb...bbb ccc...ccc u vxy

z 32

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 1: v and y consist from only a

m m m aaa...aaa bbb...bbb ccc...ccc u vxy

z 33

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 1: Repeating v and y

k 1 m m mk aaaaaa...aaaaaa bbb...bbb ccc...ccc

u

2

v xy

2

z 34

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 1: From Pumping Lemma: uv xy z  L 2

2

k 1 m m mk aaaaaa...aaaaaa bbb...bbb ccc...ccc

u

2

v xy

2

z 35

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 1: From Pumping Lemma: uv xy z  L 2

2

k 1 However:

uv xy z  a 2

2

m k m m

b c L

Contradiction!!! 36

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

Case 2:

vxy

| vxy | m is within

b

| vy | 1 m

m m m aaa...aaa bbb...bbb ccc...ccc u

vxy

z 37

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 2: Similar analysis with case 1

m m m aaa...aaa bbb...bbb ccc...ccc u

vxy

z 38

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

Case 3:

vxy

| vxy | m is within

c

| vy | 1 m

m m m aaa...aaa bbb...bbb ccc...ccc u vxy z 39

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 3: Similar analysis with case 1

m m m aaa...aaa bbb...bbb ccc...ccc u

vxy z 40

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

Case 4:

vxy

| vxy | m overlaps

a

m

| vy | 1 and

b

m

m m m aaa...aaa bbb...bbb ccc...ccc z u vxy 41

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: Possibility 1: v contains only a

y

contains only

b

m m m aaa...aaa bbb...bbb ccc...ccc z u vxy 42

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: Possibility 1: v contains only a

y

contains only

b

k1  k2  1 m m  k2 m  k1 aaa...aaaaaaa bbbbbbb...bbb ccc...ccc

u

2

v xy

2

z 43

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: From Pumping Lemma: uv xy z  L 2

2

k1  k2  1 m m  k2 m  k1 aaa...aaaaaaa bbbbbbb...bbb ccc...ccc

u

2

v xy

2

z 44

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: From Pumping Lemma: uv xy z  L 2

2

k1  k2  1 However:

uv xy z  a 2

2

m k1 m k2 m

b

c L

Contradiction!!! 45

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: Possibility 2: v contains a and b

y

contains only

b

m m m aaa...aaa bbb...bbb ccc...ccc z u vxy 46

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: Possibility 2: v contains a and b

y contains only b k1  k2  k  1 k1 k2 m mk m aaa...aaaaabbaabb bbbbbbb...bbb ccc...ccc u

2

v xy

2

z 47

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: From Pumping Lemma: uv xy z  L 2

2

k1  k2  k  1 k1 k2 m mk m aaa...aaaaabbaabb bbbbbbb...bbb ccc...ccc

u

2

v xy

2

z 48

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: From Pumping Lemma: uv xy z  L 2

However:

2

2

uv xy z

2

k1  k2  k  1 m k1 k2 m k m a b a b c L Contradiction!!! 49

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: Possibility 3: v contains only a

y

contains

a

and

b

m m m aaa...aaa bbb...bbb ccc...ccc z u vxy 50

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 4: Possibility 3: v contains only a

y

contains

a

and

b

Similar analysis with Possibility 2 51

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

Case 5:

vxy

| vxy | m overlaps

b

m

| vy | 1 and

c

m

m m m aaa...aaa bbb...bbb ccc...ccc z u vxy 52

L  {a b c : n  0} n n n

wa b c w  uvxyz

m m m

| vxy | m

| vy | 1

Case 5: Similar analysis with case 4

m m m aaa...aaa bbb...bbb ccc...ccc z u vxy 53

There are no other cases to consider

(since

| vxy | m

overlap

m

, string

m

a , b and c

vxy

m

cannot

at the same time)

54

In all cases we obtained a contradiction

Therefore: The original assumption that

L  {a b c : n  0} n n n

is context-free must be wrong

Conclusion:

L is not context-free 55