More Applications Of The Pumping Lemma

More Applications of the Pumping Lemma

1

The Pumping Lemma: • Given a infinite regular language • there exists an integer • for any string • we can write

• with

w L

L

m

with length

| w| m

w x y z

| x y |  m and | y |  1

• such that:

xy z  L i

i  0, 1, 2, ... 2

Non-regular languages

L  {vv : v  *} R

Regular languages

3

Theorem: The language

L  {vv : v  *} R

  {a, b}

is not regular

Proof:

Use the Pumping Lemma

4

L  {vv : v  *} R

Assume for contradiction that L is a regular language

Since L is infinite we can apply the Pumping Lemma 5

L  {vvR : v  *}

Let

m

be the integer in the Pumping Lemma

Pick a string

w

such that:

w L length

We pick

and

| w| m

wa b b a

m m m m 6

Write

a b b a xyz m m m m

From the Pumping Lemma it must be that length | x

m

y |  m, | y | 1

m m m

xyz  a...aa...a...ab...bb...ba...a

x Thus:

y

z

y  a , k 1 k

7

x y za b b a

y  a , k 1

m m m m

k

From the Pumping Lemma:

xy z  L i

i  0, 1, 2, ...

Thus:

xy z  L 2

8

x y za b b a

y  a , k 1

m m m m

k

From the Pumping Lemma:

xy z  L 2

m m m

m+k 2

xy z = a...aa...aa...a...ab...bb...ba...a ∈ L

x Thus:

y a

y m k m m m

b b a

z

L 9

a BUT:

m k m m m

b b a

L

k 1

L  {vv : v  *} R

a

m k m m m

b b a

L

CONTRADICTION!!! 10

Therefore:

Our assumption that L is a regular language is not true

Conclusion: L is not a regular language

11

Non-regular languages

n l n l

L  {a b c

: n, l  0}

Regular languages

12

Theorem: The language L  {a nbl cnl : n, l  0}

is not regular

Proof:

Use the Pumping Lemma

13

n l n l

L  {a b c

: n, l  0}

Assume for contradiction that L is a regular language

Since L is infinite we can apply the Pumping Lemma 14

n l n l

L  {a b c Let

m

: n, l  0}

be the integer in the Pumping Lemma

Pick a string

w

such that:

w L length

We pick

and

| w| m

wa b c

m m 2m 15

Write

m m 2m

a b c

xyz

From the Pumping Lemma it must be that length | x

m

y |  m, | y | 1

m

2m

xyz  a...aa...aa...ab...bc...cc...c

x Thus:

y

z

y  a , k 1 k

16

x y za b c

m m 2m

From the Pumping Lemma:

y  a , k 1 k

xy z  L i

i  0, 1, 2, ... Thus:

0

x y z = xz ∈ L 17

x y za b c

y  a , k 1

m m 2m

k

xz  L

From the Pumping Lemma:

mk

m

2m

xz  a...aa...ab...bc...cc...c  L

x Thus:

z

a

mk m 2 m

b c

L 18

a

BUT:

mk m 2 m

b c

n l n l

L  {a b c

a

mk m 2 m

b c

L

k 1

: n, l  0}

L

CONTRADICTION!!! 19

Therefore:

Our assumption that L is a regular language is not true

Conclusion: L is not a regular language

20

Non-regular languages

L  {a : n  0} n!

Regular languages

21

Theorem: The language

L  {a : n  0} n!

is not regular

n!  1  2  (n  1)  n

Proof:

Use the Pumping Lemma

22

L  {a : n  0} n!

Assume for contradiction that L is a regular language

Since L is infinite we can apply the Pumping Lemma 23

L  {a : n  0} n!

Let

m

be the integer in the Pumping Lemma

Pick a string

w

such that:

w L length

We pick

wa

| w| m

m! 24

Write

a

m!

xyz

From the Pumping Lemma it must be that length | x

m xyz  a

m!

y |  m, | y | 1

m!m

 a...aa...aa...aa...aa...a x

Thus:

y

z

y  a , 1 k  m k

25

x y za

y  a , 1 k  m

m!

k

From the Pumping Lemma:

xy z  L i

i  0, 1, 2, ... Thus:

xy z  L 2

26

x y za

y  a , 1 k  m

m!

k

From the Pumping Lemma:

mk

xy z  L 2

m!m

xy z  a...aa...aa...aa...aa...aa...a  L 2

x Thus:

y

y a

m! k

z

L 27

a Since:

m! k

L

1 k  m

L  {a : n  0} n!

There must exist

p

such that:

m! k  p! 28

However:

m! k  m! m  m! m!

for

m 1

 m!m  m!  m!(m  1)  (m  1)!

m! k  (m  1)! m! k  p!

for any

p 29

a BUT:

m! k

L

1 k  m

L  {a : n  0} n!

a

m! k

L

CONTRADICTION!!! 30

Therefore:

Our assumption that L is a regular language is not true

Conclusion: L is not a regular language

31